Answer: Achieving a \(g^{1/2-\epsilon}\)-approximation is \(\mathsf{NP}\)-hard for every fixed \(0<\epsilon<1/2\), even with \(\tau=1\); no polynomial-time algorithm exists unless \(\mathsf P=\mathsf{NP}\).
Theorem 36 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateTable 3: Achieved polynomial-time inapproximability results depending on the number g of groups. The larger g compared to m, the higher is the approximation ratio excluded. problem (which is polynomial-time solvable when there are no groups as it can be solved using dynamic programming via equivalence to Unary Knapsack [TF19]). Following our parameterized tractability res- ults, a PB election designer can practically use our group structures, albeit perhaps not with an arbitrary number of groups of unlimited structural complexity.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given projects \(P\) with costs \(c(p)\), global budget \(B\), project groups \(\mathcal F\) with limits \(b(G)\), and a finite-support distribution \(\mu\) with binary-rational masses over approval types \(A\subseteq P\), choose a feasible bundle \(X\subseteq P\) maximizing \(U_\mu(X)=\sum_A\mu_A|A\cap X|\). For each fixed \(\epsilon>0\), is a polynomial-time \(g^{1/2-\epsilon}\)-approximation impossible unless \(P=NP\), even when \(g=|\mathcal F|\le m^2\) and \(m=|P|\)?
Given a project set \(P\), let \(m=|P|\). Costs \(c(p)\), global budget \(B\), and group limits \(b(G)\) are binary-encoded nonnegative integers. The explicitly listed family \(\mathcal F\subseteq 2^P\) has distinct groups, with \(b(G)\le B\) and \(1\le g=|\mathcal F|\le m^2\).
A society is given by its support: the list of the \(\tau\) distinct approval types \(A\subseteq P\) with positive mass, each mass \(\mu_A\) a binary rational, with \(\sum_A\mu_A=1\). Here \(\tau\) is the support size, not the number of possible approval types. Every project belongs to some supported approval type.
A bundle \(X\subseteq P\) is feasible exactly when \(\sum_{p\in X}c(p)\le B\) and \(\sum_{p\in X\cap G}c(p)\le b(G)\) for every \(G\in\mathcal F\). Maximize \(U_\mu(X)=\sum_A\mu_A|A\cap X|\). Projects are indivisible.
Let \(\mathrm{OPT}\) be the maximum feasible utility. An approximation factor \(\alpha\ge1\) requires a feasible bundle of utility at least \(\mathrm{OPT}/\alpha\). Let \(L\) be the total input bit length; state running times in \(m,\tau,g,L\) and any dependence on \(\epsilon\).
For each fixed \(0<\epsilon<1/2\), does this problem admit a \(g^{1/2-\epsilon}\)-approximation in time polynomial in \(m,\tau,g,L\), or is achieving this factor NP-hard, excluding such an algorithm unless \(\mathsf P=\mathsf{NP}\)?
For explicitly listed finite voters, a polynomial-time \(g^{1/2-\epsilon}\)-approximation is impossible unless \(\mathsf P=\mathsf{NP}\), even when \(g\le m^2\); a polynomial-time \((g+2)\)-approximation is known. [Source](https://arxiv.org/html/2012.05213v2)
No result explicitly addressing the normalized, binary-rational support model above was identified in the literature search.
For every fixed \(0<\epsilon<1/2\), achieving a \(g^{1/2-\epsilon}\)-approximation is \(\mathsf{NP}\)-hard. This holds even with \(\tau=1\), mass \(1\), unit project costs, and groups of size \(2\).
Zuckerman proved that, for every fixed \(0<\delta<1\), approximating Maximum Clique on an \(n\)-vertex graph within \(n^{1-\delta}\) is \(\mathsf{NP}\)-hard. [Zuckerman, Theorem 1.1](https://theoryofcomputing.org/articles/v003a006/v003a006.pdf).
Consequently, the same statement holds for Maximum Independent Set: a subset is independent in a graph exactly when it is a clique in its complement. Taking complements preserves the vertex count and solution cardinalities and takes polynomial time.
Let \(H=(V,E)\) be a simple graph with \(n=|V|\). If \(E=\varnothing\), its maximum independent set is \(V\), which we can return exactly. Thus, to construct an approximation algorithm for arbitrary graphs, it suffices to handle graphs with \(E\ne\varnothing\).
For such a graph, construct the budgeting instance as follows:
All input conditions hold. The groups are distinct because the graph is simple. Furthermore, \(1\le g=|E|\le\binom n2\le m^2\), and every group limit is at most \(B\). The support consists of one distinct type with positive binary-rational mass summing to \(1\), and every project belongs to that type.
Feasibility equivalence. The global constraint holds for every \(X\subseteq P\), since its cost is \(|X|\le n\). For an edge \(e=\{u,v\}\), its group constraint is precisely \(|X\cap\{u,v\}|\le1\). Thus \(X\) is feasible if and only if it contains no two adjacent vertices, equivalently, if and only if it is an independent set of \(H\).
Objective equivalence. For every bundle, \(U_\mu(X)=\mu_P|P\cap X|=|X|\). Writing \(a(H)\) for the maximum independent-set cardinality, we therefore have \(\mathrm{OPT}=a(H)\). The correspondence preserves both feasibility and objective values exactly.
Fix \(0<\epsilon<1/2\). Suppose an algorithm always returns a feasible bundle satisfying \(U_\mu(X)\ge\mathrm{OPT}/g^{1/2-\epsilon}\), in time polynomial in \(m,\tau,g,L\).
Applying it to the constructed instance gives an independent set with
\(\displaystyle |X|\ge\frac{a(H)}{g^{1/2-\epsilon}}\ge\frac{a(H)}{n^{1-2\epsilon}}.\)
The second inequality follows from \(g\le n^2\) and \(1/2-\epsilon>0\), which imply \(g^{1/2-\epsilon}\le(n^2)^{1/2-\epsilon}=n^{1-2\epsilon}\).
For completeness, using incidence vectors for the explicitly listed groups, the construction has input length \(L=O(mg+m\log m)=O(n^3)\) and can be produced within the same bit-operation bound. Here \(\tau=1\) and \(g\le n^2\). Hence any running time polynomial in \(m,\tau,g,L\) becomes polynomial in \(n\). Its constants and polynomial degree may depend arbitrarily on the fixed \(\epsilon\); the reduction itself does not depend on \(\epsilon\).
Together with the exact treatment of edgeless graphs, this would give a polynomial-time \(n^{1-2\epsilon}\)-approximation for Maximum Independent Set. Taking \(\delta=2\epsilon\in(0,1)\) contradicts the stated hardness theorem unless \(\mathsf P=\mathsf{NP}\).
There is also a direct transfer from explicitly listed voters. For \(N\) voters, let \(k_A\) count those with approval type \(A\), and retain each occurring type once with mass \(\mu_A=k_A/N\). Then
\(\displaystyle U_\mu(X)=\frac1N\sum_{v=1}^{N}|A_v\cap X|.\)
Feasibility is unchanged, and both the optimum and every bundle’s utility are scaled by \(1/N\), preserving every multiplicative approximation factor. There are at most \(N\) supported types, and each mass needs \(O(\log N)\) bits, so this conversion is polynomial in the explicit-voter input length. This transfers the supplied finite-voter hardness theorem as well. [Jain et al., Theorem 36](https://arxiv.org/html/2012.05213v2#S6).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes the requested hardness for the normalized, binary-rational support model, even with \(\tau=1\). No mathematical errors or substantive gaps were found.
The prover states the required theorem correctly: for every fixed \(0<\delta<1\), approximating Maximum Clique on an \(n\)-vertex graph within \(n^{1-\delta}\) is \(\mathsf{NP}\)-hard. This is a restriction of the range stated in [Zuckerman’s Theorem 1.1](https://theoryofcomputing.org/articles/v003a006/v003a006.pdf). The source expressly uses polynomial-time, many-one reductions, so the claimed consequence under \(\mathsf P\ne\mathsf{NP}\) is justified.
The transfer to Maximum Independent Set is valid. Complementation preserves the vertex set, and a subset is independent in the original graph exactly when it is a clique in the complement. Thus both optimum values and approximation factors are preserved.
For a simple graph with at least one edge, every constructed component satisfies the task:
The edgeless case is explicitly handled without constructing an instance with the prohibited value \(g=0\). Returning all vertices solves that case exactly.
Finding: All required domain restrictions and relevant degenerate cases are covered.
With unit costs, the global cost of any bundle is \(|X|\le n=B\).
For every edge \(\{u,v\}\), its group constraint is exactly
\[
|X\cap\{u,v\}|\le1.
\]
Consequently, satisfying every group constraint is equivalent to containing no adjacent pair. This proves both directions of the claimed equivalence between feasible bundles and independent sets.
Finding: Correct; no missing implication.
The single supported type gives
\[
U_\mu(X)=1\cdot|P\cap X|=|X|.
\]
Together with the feasibility equivalence, this establishes \(\mathrm{OPT}=a(H)\). The reduction therefore preserves individual solution values and optimum values exactly.
Finding: Correct. Normalization introduces no loss in this construction.
For fixed \(0<\epsilon<1/2\), the exponent \(1/2-\epsilon\) is positive. Hence \(g\le n^2\) implies
\[
g^{1/2-\epsilon}\le n^{1-2\epsilon}.
\]
The direction of the resulting utility bound is correct:
\[
|X|\ge\frac{a(H)}{g^{1/2-\epsilon}}
\ge\frac{a(H)}{n^{1-2\epsilon}}.
\]
Setting \(\delta=2\epsilon\) satisfies \(0<\delta<1\), exactly the stated range of the hardness theorem. The argument applies separately to every fixed permitted \(\epsilon\); it does not require uniform polynomial dependence on \(\epsilon\).
Finding: The approximation contradiction is valid.
Under the stated incidence-vector encoding, group membership requires \(O(mg)\) bits. The remaining project, budget, and support data fit within the stated \(O(m\log m)\) allowance. Thus
\[
L=O(mg+m\log m)=O(n^3).
\]
The construction can be written within that bit-operation bound. Since \(m=n\), \(\tau=1\), and \(g\le n^2\), a running time polynomial in \(m,\tau,g,L\) becomes polynomial in \(n\). Allowing its degree and constants to depend on fixed \(\epsilon\) does not weaken the contradiction.
Finding: The encoding and runtime argument is sufficient.
For a nonempty explicit electorate, the frequencies \(k_A/N\) are positive for retained types and sum to \(1\). The displayed identity scales every bundle’s utility, and therefore the optimum, by the same positive factor. Multiplicative approximation guarantees are preserved.
There are at most \(N\) retained types, and binary numerator-denominator representations require \(O(\log N)\) bits per mass. The conversion is polynomial in the explicit input length.
The cited [Jain et al. theorem and model assumptions](https://arxiv.org/html/2012.05213v2#S6) match the claimed hardness and include distinct groups, bounded group limits, and approval coverage. This supplementary transfer is consistent with the main proof.
No additional clarification, missing lemma, or repair is needed. The output resolves the assigned complexity question.
⟨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.