Answer: \(\mathrm{NP}\)-hard; indeed, \(\#\mathrm{P}\)-complete under polynomial-time parsimonious reductions for every fixed \(k\ge 2\).
Theorem 4.5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIn the unrestricted case, for each k, k ≥2, k-Approval-#CCAC and k- Approval-#CCDC are #P-complete, and k-Approval-#DCAC and k-Approval-#DCDC are #P-metric-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(C,A,p,\ell\), fixed \(k\ge 2\), and complete ranking types \(T\) over \(C\cup A\) with rational masses \(\mu_t\) summing to \(1\), compute the number of sets \(A'\subseteq A\) with \(|A'|\le\ell\) for which \(p\) is the unique \(k\)-Approval winner after restricting each type to \(C\cup A'\), where \(\operatorname{score}_{\mu,A'}(c)=\sum_{t\in T}\mu_t\mathbf{1}[c\text{ is top-}k].\)
Let \(C\) and \(A\) be disjoint finite sets of registered and available candidates, with \(p\in C\), and let \(\ell\ge 0\) be a binary-encoded integer. Fix an integer \(k\ge 2\); put \(m=|C\cup A|\).
A society is given by its support: the list of \(\tau\) distinct unrestricted strict complete ranking types over \(C\cup A\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
For each \(A'\subseteq A\), restrict rankings to \(C\cup A'\) and apply mass-weighted \(k\)-Approval: \(s_{A'}(c)=\sum_t\mu_t\mathbf{1}[c\text{ occupies one of the first }\min\{k,|C\cup A'|\}\text{ positions}]\).
Let \(N\) be the number of sets \(A'\subseteq A\) with \(|A'|\le\ell\) such that \(s_{A'}(p)>s_{A'}(c)\) for every \(c\in(C\cup A')\setminus\{p\}\). Ties do not qualify, and each candidate set is counted once.
For each fixed \(k\ge 2\), is exact computation of \(N\) possible in polynomial time in \(m,\tau,L,\ell\), or is it \(\mathrm{NP}\)-hard?
For finite explicitly listed unweighted voters, counting these successful candidate additions is \(\#\mathrm{P}\)-complete under parsimonious reductions for every fixed \(k\ge 2\). [Wojtas et al.](https://arxiv.org/pdf/1405.6630)
No separate result for exactly the normalized rational-mass support formulation was located in the literature search.
For every fixed \(k\ge 2\), exact computation of \(N\) is \(\#\mathrm{P}\)-complete under polynomial-time parsimonious reductions. In particular, it is \(\mathrm{NP}\)-hard.
The normalization and aggregation of identical rankings preserve the number of successful candidate sets exactly.
We use the following established result: for every fixed \(k\ge 2\), counting the sets of at most \(\ell\) available candidates whose addition makes \(p\) the unique \(k\)-Approval winner, with unrestricted rankings and explicitly listed unweighted voters, is \(\#\mathrm{P}\)-complete under parsimonious reductions. This is Theorem 4.5 of [Wojtas et al., *Possible Winners in Noisy Elections*](https://arxiv.org/pdf/1405.6630). Their Definition 3.1 specifies the unique-winner condition and the upper bound on the number of added candidates; their complexity convention defines \(\#\mathrm{P}\)-completeness using parsimonious reductions.
Thus the source problem counts exactly the same kind of candidate sets as the present problem. The difference is the representation of the electorate.
Fix \(k\ge 2\). Consider a source instance with candidate sets \(C,A\), designated candidate \(p\), budget \(\ell\), and \(n\ge 1\) explicitly listed voters. Each voter has a strict complete ranking over \(C\cup A\).
First replace the budget by \(\ell_0=\min\{\ell,|A|\}\). This preserves all feasible candidate sets.
Group voters having identical rankings. Let \(R_1,\ldots,R_\tau\) be the distinct rankings and let \(n_t\) be the number of voters with ranking \(R_t\). Construct the target society using these rankings with masses
\(\displaystyle \mu_t=\frac{n_t}{n}\quad(t=1,\ldots,\tau).\)
Every mass is positive, the rankings are distinct, and \(\sum_{t=1}^{\tau}\mu_t=1\). Encode each rational by its binary numerator and denominator.
Identical rankings can be grouped by sorting or pairwise comparison in polynomial time. Moreover, \(\tau\le n\), and each numerator and denominator requires at most \(O(\log(n+1))\) bits. The rankings are copied from the source input, so the entire target encoding has polynomial length in the source encoding.
The construction preserves \(C,A,p\), and \(k\), and uses budget \(\ell_0\le |A|\le m\).
Fix any \(A'\subseteq A\) and any \(c\in C\cup A'\). Let \(u_{A'}(c)\) be the unweighted score in the source election after restricting rankings to \(C\cup A'\). Define \(I_t(A',c)\) to equal \(1\) precisely when \(c\) occupies one of the first \(\min\{k,|C\cup A'|\}\) positions in restricted ranking \(R_t\), and \(0\) otherwise.
Grouping identical rankings gives
\(\displaystyle u_{A'}(c)=\sum_{t=1}^{\tau}n_t I_t(A',c).\)
The corresponding target score satisfies
\(\displaystyle s_{A'}(c)=\sum_{t=1}^{\tau}\frac{n_t}{n}I_t(A',c)=\frac{u_{A'}(c)}{n}.\)
Because \(n>0\), for every opponent \(c\),
\(\displaystyle s_{A'}(p)>s_{A'}(c)\quad\Longleftrightarrow\quad u_{A'}(p)>u_{A'}(c).\)
Consequently, each candidate set succeeds in the target instance exactly when it succeeds in the source instance. Ties are preserved as well. Since candidate sets themselves are unchanged, this is a parsimonious reduction.
For completeness, if zero-voter source instances are permitted, their count is \(1\) when \(C=\{p\}\), and \(0\) otherwise: all scores are zero, so only an election containing \(p\) alone qualifies. These cases map respectively to fixed target instances with \(A=\varnothing\), one ranking of mass \(1\), and registered sets \(\{p\}\) or \(\{p,q\}\). In the latter instance both candidates receive approval because \(k\ge 2\).
The cited theorem and this reduction establish \(\#\mathrm{P}\)-hardness.
A witness is the characteristic vector of a subset \(A'\subseteq A\). This uses exactly \(|A|\) bits and represents each candidate set once.
The verifier first checks \(|A'|\le\ell\), then computes the scores and checks all required strict inequalities. We verify that these computations take polynomial bit complexity.
Write each input mass as \(\mu_t=a_t/b_t\), with positive binary integers \(a_t,b_t\). Set
\(\displaystyle D=\prod_{t=1}^{\tau}b_t,\qquad w_t=a_t(D/b_t).\)
These are integers, and normalization implies \(\sum_t w_t=D\). The bit length of \(D\) is bounded by \(\sum_t\operatorname{bitlength}(b_t)\), hence by \(O(L)\). All products and exact divisions therefore take polynomial time.
For each candidate define the integer score
\(\displaystyle S_{A'}(c)=\sum_{t=1}^{\tau}w_t I_t(A',c).\)
It satisfies \(S_{A'}(c)=D\,s_{A'}(c)\) and \(0\le S_{A'}(c)\le D\). Thus score comparisons involve integers with \(O(L)\) bits. Scanning each listed ranking determines its approved candidates after restriction in \(O(m)\) steps, giving polynomial verification time overall.
A nondeterministic machine guesses the \(|A|\)-bit characteristic vector and accepts exactly when this verifier succeeds. It has exactly \(N\) accepting branches. Hence \(N\in\#\mathrm{P}\).
Combining hardness and membership proves \(\#\mathrm{P}\)-completeness.
The decision problem \(N>0\) is also \(\mathrm{NP}\)-complete: it has the verifier above, and a parsimonious reduction from counting satisfying assignments preserves whether the count is positive. Computing \(N\) exactly therefore decides an \(\mathrm{NP}\)-complete problem.
Finally, allowing running time polynomial in the *numerical value* of \(\ell\) does not avoid this hardness. Every instance can be replaced by an equivalent one with \(\ell\le |A|\le m\), as in the reduction. Such an exact algorithm would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. For every fixed \(k\ge 2\), the argument establishes \(\#\mathrm{P}\)-completeness under polynomial-time parsimonious reductions for the normalized rational-mass support formulation. No major or minor mathematical issues were found.
Theorem 4.5 states that unrestricted \(k\)-Approval constructive control by adding candidates is \(\#\mathrm{P}\)-complete for every \(k\ge 2\). Definition 3.1 counts subsets of available candidates of size at most the budget that make the designated candidate the unique winner. The paper explicitly uses “\(\#\mathrm{P}\)-complete” to mean completeness under parsimonious reductions. Thus the prover correctly identifies the theorem, winner convention, budget condition, and reduction type. [Wojtas et al., Definitions 2.3 and 3.1 and Theorem 4.5](https://arxiv.org/pdf/1405.6630)
The source rankings are unrestricted complete orders, as required. Its approval rule counts candidates ranked among the top \(k\); for an election with fewer than \(k\) candidates, this agrees with approving the first \(\min\{k,|C\cup A'|\}\) candidates.
Replacing \(\ell\) by \(\ell_0=\min\{\ell,|A|\}\) preserves the feasible subsets because every subset of \(A\) already has size at most \(|A|\).
For \(n>0\), grouping identical rankings yields distinct support types with positive multiplicities \(n_t\). Consequently, the masses \(\mu_t=n_t/n\) are positive rational numbers and sum to one.
The size bound is correct: \(\tau\le n\), and both numerator and denominator have \(O(\log(n+1))\) bits. Because the voters are explicitly listed, grouping and copying their rankings takes polynomial time in the source input length. The reduction requires no expansion of a succinct electorate.
For each fixed subset \(A'\) and each participating candidate \(c\), identical full rankings also have identical restrictions. Hence the displayed identity
\(u_{A'}(c)=\sum_t n_t I_t(A',c)\)
is valid.
Substituting the constructed masses gives
\(s_{A'}(c)=u_{A'}(c)/n\).
Division by the positive number \(n\) preserves every strict comparison and every tie. The candidate sets and their feasibility conditions are unchanged. Therefore the reduction preserves the count exactly, rather than merely preserving existence.
With no voters, all scores are zero. Since \(p\in C\), a unique winner is possible exactly when \(C=\{p\}\) and \(A'=\varnothing\). This gives precisely the claimed counts.
Both proposed fixed target instances have valid normalized support. The instance with registered set \(\{p\}\) has count one. The instance with registered set \(\{p,q\}\) has count zero because \(k\ge 2\) makes both candidates approved and tied. Thus this boundary case does not obstruct parsimony.
A characteristic vector of length \(|A|\) represents each subset exactly once.
The common denominator \(D=\prod_t b_t\) has bit length at most the sum of the denominator bit lengths, which is \(O(L)\). Each \(w_t=a_t(D/b_t)\) is an integer, and normalization gives \(\sum_t w_t=D\). Therefore each integer score lies between zero and \(D\), and all arithmetic and strict comparisons have polynomial bit complexity.
Scanning each complete ranking correctly identifies the first eligible candidates after restriction, including elections with fewer than \(k\) candidates. The resulting deterministic verifier runs in polynomial time. Guessing exactly one characteristic vector per branch consequently produces exactly \(N\) accepting branches.
Parsimonious hardness and membership establish the claimed \(\#\mathrm{P}\)-completeness. Parsimonious reductions preserve positivity of the count, so the stated NP-completeness of deciding \(N>0\) also follows.
The numerical-budget observation is correct: the reduction always outputs \(\ell_0\le m\). An exact algorithm polynomial in \(m,\tau,L,\ell\) would therefore run in polynomial time on these hard instances and imply \(\mathrm{P}=\mathrm{NP}\).
No additional clarification or repair is needed.
⟨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.