Answer: \(\mathrm{NP}\text{-hard}\); deciding existence is \(\mathrm{NP}\text{-complete}\).
Proposition 3.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing Strong-BJR-L and Strong-BPJR-L budgets is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite project set \(C\), integer costs \(w\), budget limit \(L\), finite approval-type set \(T\subseteq 2^C\), and rational distribution \(\mu\) over \(T\), find an indivisible budget \(W\subseteq C\) with \(w(W)\le L\) satisfying continuous Strong-BJR-\(L\), or report that none exists. The condition forbids a submass \(\nu\) with \(0\le\nu_A\le\mu_A\), \(\sum_A\nu_A\ge 1/L\), \(w(\bigcap_{\nu_A>0}A)\ge1\), and \(w((\bigcup_{\nu_A>0}A)\cap W)=0\).
Let \(C\) be a finite project set, \(w:C\to\mathbb Z_{>0}\) a cost function, and \(L\in\mathbb Z_{>0}\) a budget limit. Write \(w(S)=\sum_{c\in S}w(c)\). The input also gives an explicit finite set \(T\subseteq 2^C\) of approval types and a rational distribution \(\mu\) over \(T\).
An indivisible budget \(W\subseteq C\) is feasible when \(w(W)\le L\). It satisfies continuous Strong-BJR-\(L\) if there is no submass \(\nu\) with \(0\le\nu_A\le\mu_A\), \(\sum_{A\in T}\nu_A\ge 1/L\), \(w(\bigcap_{\nu_A>0}A)\ge1\), and \(w((\bigcup_{\nu_A>0}A)\cap W)=0\).
Is the problem of finding such a budget, or reporting that none exists, solvable in polynomial time or NP-hard?
For finite voter lists, computing a Strong-BJR-\(L\) budget is NP-hard, and a satisfying budget need not exist.
The problem is \(\mathrm{NP}\)-hard. In fact, deciding whether a satisfying feasible budget exists is \(\mathrm{NP}\)-complete, even with equal project costs, a uniform distribution, and exactly two projects in every approval type.
For a budget \(W\subseteq C\) and a project \(c\in C\), define
\(r_c(W)=\sum_{\substack{A\in T\\c\in A,\ A\cap W=\varnothing}}\mu_A\).
Lemma. A feasible budget \(W\) satisfies continuous Strong-BJR-\(L\) if and only if \(r_c(W)<1/L\) for every \(c\in C\).
Proof. Suppose a blocking submass \(\nu\) exists. Its support is nonempty because its total mass is positive. Since project costs are positive integers, the condition on the intersection implies that some project \(c\) belongs to every supported type. The zero-cost condition on the represented union implies that every supported type is disjoint from \(W\). Consequently,
\(r_c(W)\ge\sum_{A\in T}\nu_A\ge1/L\).
Conversely, suppose \(r_c(W)\ge1/L\). Set \(\nu_A=\mu_A\) whenever \(c\in A\) and \(A\cap W=\varnothing\), and set \(\nu_A=0\) otherwise. This submass has total mass at least \(1/L\). Every supported type contains \(c\), so their intersection has cost at least \(w(c)\ge1\). Every supported type is disjoint from \(W\), so their union has zero represented cost. Thus \(\nu\) blocks \(W\). This proves the lemma.
A proposed budget can therefore be verified by checking feasibility and computing these rational sums. Exact rational arithmetic takes polynomial time: a common denominator obtained by multiplying the input denominators has bit length at most their total bit length. Hence the existence problem belongs to \(\mathrm{NP}\).
Reduce from Vertex Cover: given a finite simple undirected graph \(G=(V,E)\) and an integer \(k\), determine whether some set of at most \(k\) vertices meets every edge. This is the classical \(\mathrm{NP}\)-complete Node Cover problem in [Karp’s paper](https://studylib.net/doc/27985824/karp1972).
We may restrict to \(m=|E|\ge1\) and \(1\le k\le|V|\); excluded cases are directly decidable and can be replaced by fixed instances with the same answer.
Construct the budgeting instance as follows:
Because the graph is simple, these are distinct types. Their masses sum to one. The construction has polynomial encoding length, and every project is individually affordable because \(m\le km=L\).
For every \(W\subseteq V\), feasibility is equivalent to \(m|W|\le km\), hence to \(|W|\le k\).
If \(W\) is a vertex cover, every approval type intersects \(W\). Thus \(r_c(W)=0\) for every project \(c\), and the lemma shows that \(W\) satisfies continuous Strong-BJR-\(L\).
If \(W\) is not a vertex cover, some edge \(e=\{u,v\}\) has neither endpoint in \(W\). Define a submass by \(\nu_{A_e}=1/m\) and \(\nu_A=0\) for every other type. Its total mass satisfies
\(1/m\ge1/(km)=1/L\).
Its supported intersection is \(A_e\), of cost \(2m\ge1\), while its supported union is disjoint from \(W\). It therefore blocks \(W\).
Consequently, the constructed instance has a satisfying feasible budget if and only if \(G\) has a vertex cover of size at most \(k\).
The reduction proves \(\mathrm{NP}\)-hardness of existence; polynomial verification proves \(\mathrm{NP}\)-completeness. An algorithm that always finds a satisfying feasible budget or correctly reports nonexistence would decide Vertex Cover through this construction. Thus the requested task is \(\mathrm{NP}\)-hard and has no polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct. The argument establishes that existence is \(\mathrm{NP}\)-complete and that the requested task of finding a satisfying budget or reporting nonexistence is \(\mathrm{NP}\)-hard. No substantive or minor gaps require repair.
The forward implication is valid. Since \(L>0\), a blocking submass has positive total mass and therefore nonempty support. Positive integer costs imply that an intersection of cost at least \(1\) contains some project \(c\). The zero represented-cost condition implies that every supported approval type is disjoint from \(W\), because every project has strictly positive cost.
Thus every supported type contributes its full available mass to \(r_c(W)\), and the coordinatewise bounds \(\nu_A\le\mu_A\) justify
\(r_c(W)\ge\sum_{A\in T}\nu_A\ge1/L\).
The reverse implication is also valid. The proposed submass satisfies every coordinatewise bound and has sufficiently large total mass. Its support is nonempty, every supported type contains \(c\), and every supported type avoids \(W\). Consequently, both blocking conditions hold.
Using the entire available mass is legitimate: the definition requires total mass at least \(1/L\), not exactly \(1/L\). The strict inequality in the satisfaction criterion is therefore correct, including the equality boundary.
A subset \(W\subseteq C\) has a polynomial-size encoding. Feasibility can be checked by integer addition and comparison. Since approval types are explicit, all required membership and disjointness checks take polynomial time.
The rational-arithmetic justification is sound. Multiplying the input denominators produces a common denominator with polynomial bit length; the corresponding numerators and their sums also have polynomial bit length. Exact comparison with \(1/L\) is consequently polynomial-time. This establishes membership in \(\mathrm{NP}\) for the existence problem, despite the definition quantifying over continuous submasses.
The stated Vertex Cover decision problem is the standard \(\mathrm{NP}\)-complete problem. The cited paper lists Node Cover among its complete problems and specifies the edge-covering condition used here. [Karp’s paper](https://studylib.net/doc/27985824/karp1972)
Restricting to \(m\ge1\) and \(1\le k\le|V|\) is legitimate. The excluded cases are directly decidable, as stated. Replacing them with fixed instances of the same answer is routine and does not require an additional mathematical argument.
All construction requirements are met:
The feasibility equivalence \(w(W)\le L\) if and only if \(|W|\le k\) follows correctly by cancelling the positive factor \(m\).
If \(W\) is a vertex cover, every approval type intersects \(W\). Hence every residual mass \(r_c(W)\) is zero, and the characterization proves satisfaction.
If \(W\) is not a vertex cover, the selected uncovered edge supplies a valid blocking submass. Its mass satisfies \(1/m\ge1/(km)\) because \(k\ge1\). Its supported intersection contains its two distinct endpoints and has cost \(2m\ge1\). Its supported union avoids \(W\). Every required condition is checked.
In particular, when \(k=1\), the mass inequality becomes equality, which still blocks under the stated definition. Isolated vertices do not affect either direction.
The equivalence between feasible satisfying budgets and vertex covers of size at most \(k\) establishes a polynomial-time reduction to existence. Combined with polynomial verification, it proves \(\mathrm{NP}\)-completeness of existence under all three advertised restrictions.
An algorithm that always returns a satisfying feasible budget or correctly reports nonexistence would decide these existence instances, and therefore Vertex Cover. The claimed hardness of the requested task follows.
No corrective feedback is necessary.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.