Answer: polynomial-time solvable
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe $q$-NCSA rule has the following properties for all $q \in [0,1]$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates \(C\) and a finite-support distribution \(\mu\) over approval ballots \(A\subseteq C\), with binary-rational masses summing to \(1\), let \(a_c=\sum_{A:c\in A}\mu_A\). For \(q=\tfrac12\), return a largest-cardinality shortlist \(S\subseteq C\) maximizing \(\Phi_\mu(S)=\frac{\sum_{c\in S}(2a_c-1)}{\sqrt{|S|}}\) for nonempty \(S\), with \(\Phi_\mu(\emptyset)=0\).
A society is given by its support: a list of \(\tau\) distinct approval types \(A\subseteq C\) with positive binary-rational masses \(\mu_A\) summing to \(1\). Here \(C\) has \(m\geq2\) candidates; \(\tau\) is the support size, not the number of possible approval types. Let \(L\) be the total input bit length.
Define \(a_c=\sum_{A:c\in A}\mu_A\), and assume that these approval masses are not all equal. Empty approval ballots are permitted.
Fix \(q=\tfrac12\). For nonempty \(S\subseteq C\), define \(\Phi_\mu(S)=\frac{\sum_{c\in S}(2a_c-1)}{\sqrt{|S|}}\), and set \(\Phi_\mu(\emptyset)=0\).
The required output is a set maximizing \(\Phi_\mu\) over all subsets of \(C\), with maximum cardinality among the maximizers.
Is computing this shortlist solvable in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For an explicitly listed finite electorate, \(\tfrac12\)-NCSA with maximum-cardinality tie-breaking is polynomial-time computable. This established result concerns explicit voter lists, rather than binary-rational support input.
The shortlist is computable in time polynomial in \(m,\tau,L\). Sorting the approval masses reduces the optimization to \(m+1\) sets, and their objective values can be compared exactly using integer arithmetic.
Define \(w_c=2a_c-1\). Order the candidates as \(c_1,\ldots,c_m\) so that \(w_{c_1}\geq\cdots\geq w_{c_m}\), breaking equal-weight ties arbitrarily. Let \(P_0=\emptyset\) and \(P_k=\{c_1,\ldots,c_k\}\) for \(1\leq k\leq m\).
For every set \(S\) of cardinality \(k\geq1\),
\(\displaystyle \sum_{c\in S}w_c\leq\sum_{i=1}^{k}w_{c_i}.\)
Indeed, if the indices of its candidates are \(i_1<\cdots<i_k\), then \(i_j\geq j\), and the ordering gives \(w_{c_{i_j}}\leq w_{c_j}\) for each \(j\). Dividing by the positive number \(\sqrt{k}\) therefore gives
\(\displaystyle \Phi_\mu(S)\leq\Phi_\mu(P_k).\)
Consequently, the maximum over all subsets equals the maximum over \(P_0,\ldots,P_m\).
This reduction also preserves maximum-cardinality tie-breaking. If a globally maximizing set has cardinality \(k\), the preceding inequality implies that \(P_k\) is also globally maximizing: its value is at least that of the given set and cannot exceed the global maximum. Thus the largest index \(k\) of a maximizing prefix is exactly the largest cardinality of any maximizing set.
Write each input mass in its binary rational representation as \(\mu_A=p_A/d_A\), with positive integers \(p_A,d_A\). Set
\(\displaystyle D=\prod_{A\text{ in the support}}d_A,\qquad u_A=p_A(D/d_A).\)
Each \(u_A\) is an integer, and normalization gives \(\sum_Au_A=D\). For every candidate define
\(\displaystyle z_c=2\sum_{A:c\in A}u_A-D.\)
Then \(w_c=z_c/D\). Because \(0\leq a_c\leq1\), we also have \(-D\leq z_c\leq D\).
Sort candidates by decreasing \(z_c\), which is the same ordering as by decreasing \(w_c\), and define
\(\displaystyle Z_0=0,\qquad Z_k=\sum_{i=1}^{k}z_{c_i}\quad(1\leq k\leq m).\)
For every nonempty prefix,
\(\displaystyle \Phi_\mu(P_k)=\frac{Z_k}{D\sqrt{k}}.\)
Although this value may be irrational, no approximation is needed to compare it with another prefix value.
Initialize the best index as \(b=0\), representing the empty set and its value \(0\). Process indices \(k=1,\ldots,m\) in increasing order.
If \(Z_k<0\), discard this prefix: its value is negative, whereas the current best value is nonnegative.
Otherwise, define \(r_b=1\) when \(b=0\), and \(r_b=b\) when \(b>0\). In both cases, the current best value is \(Z_b/(D\sqrt{r_b})\). Its numerator and \(Z_k\) are nonnegative. Hence squaring preserves their ordering, and
\(\displaystyle \frac{Z_k}{D\sqrt{k}}\geq\frac{Z_b}{D\sqrt{r_b}} \quad\Longleftrightarrow\quad r_bZ_k^2\geq kZ_b^2. \)
Compare these two integers. Replace \(b\) by \(k\) when the left-hand side is larger or equal.
Inductively, after processing index \(k\), the stored prefix has the greatest objective value among \(P_0,\ldots,P_k\), and the largest cardinality among prefixes attaining that value. Negative prefixes cannot improve the stored value; for nonnegative prefixes the integer comparison is exact; and equality favors the newly processed, larger index.
Return \(P_b\). Section 1 proves that this set satisfies both requirements over all subsets.
This procedure also handles zero-valued optima. A prefix with \(Z_k=0\) ties the empty set exactly, so the algorithm selects the largest such prefix unless a positive-valued prefix exists.
The bit length of \(D\) is at most \(1+\sum_A\log_2 d_A\), which is \(O(L)\). Normalization implies \(0<u_A\leq D\), so every \(u_A\) and \(z_c\) has \(O(L)\) bits. Since \(|Z_k|\leq mD\), each prefix sum has \(O(L+\log m)\) bits.
Every comparison uses integers of magnitude at most \(m^3D^2\), and therefore also of bit length \(O(L+\log m)\). Exact addition, multiplication, division, and comparison of these integers take polynomial time using elementary integer algorithms.
Constructing \(D\) and the \(u_A\) requires \(O(\tau)\) arithmetic operations. Computing all candidate sums requires at most \(O(m\tau)\) additions and incidence checks. Sorting requires \(O(m\log m)\) integer comparisons, and scanning the prefixes requires \(O(m)\) further arithmetic operations. The total running time is therefore polynomial in \(m,\tau,L\).
The algorithm processes the rational support directly and never expands it into a voter list. The assumption that approval masses are not all equal is unnecessary for this proof; the algorithm works in that case as well.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes polynomial-time solvability in \(m,\tau,L\). The argument is rigorous, handles maximum-cardinality tie-breaking, and uses exact arithmetic with polynomially bounded bit lengths. No major or minor issues were found.
The candidate ordering and prefix definitions are valid, including arbitrary ordering among candidates with equal weights.
For a set of cardinality \(k\), its ordered candidate indices satisfy \(i_j\geq j\). Thus the stated inequalities \(w_{c_{i_j}}\leq w_{c_j}\) hold term by term. Summing and dividing by the positive denominator \(\sqrt{k}\) correctly proves that the corresponding prefix has at least as large an objective value.
Including \(P_0=\emptyset\) therefore reduces the global optimization to the stated \(m+1\) prefixes.
The tie-breaking argument is also correct. Whenever a globally maximizing set has cardinality \(k\), the prefix \(P_k\) must attain the same global maximum. Consequently, the largest maximizing prefix index equals the largest cardinality of any maximizing set. Arbitrary equal-weight ordering does not affect this conclusion.
Under the stated binary encoding of rational masses, writing each mass as \(p_A/d_A\) is valid. The product \(D\) is positive and divisible by every \(d_A\), so each \(u_A\) is an integer.
Normalization correctly yields \(\sum_A u_A=D\). The identity \(w_c=z_c/D\) follows directly from the definitions. Positivity and normalization of the masses imply \(0\leq a_c\leq1\), verifying the bound \(-D\leq z_c\leq D\).
Sorting by \(z_c\) therefore gives precisely the required weight ordering. The displayed formula for each prefix objective is correct.
Empty approval ballots cause no difficulty: their masses contribute to \(D\) and normalization, but to no candidate approval sum.
The maintained best value is always nonnegative because initialization includes the empty set. Discarding a negative-valued prefix is therefore justified.
For a remaining prefix, both comparison numerators are nonnegative. Squaring preserves their ordering, and multiplication by the positive denominators gives exactly the stated comparison:
\[ r_b Z_k^2\geq kZ_b^2. \]
The convention \(r_0=1\), together with \(Z_0=0\), correctly represents the empty-set value without introducing division by zero.
The induction invariant stated by the prover follows from the exact comparison and the rejection of negative prefixes.
Processing indices in increasing order and replacing the stored index on equality selects the largest cardinality among maximizing prefixes. Combined with Section 1, this establishes both required properties over all subsets.
The treatment of zero-valued optima is correct. If all nonempty prefix values are negative, initialization also correctly leaves the empty set selected.
All stated magnitude and bit-length bounds are valid:
Thus every arithmetic operation involves polynomially bounded bit lengths. The construction, candidate aggregation, sorting, and scan use polynomially many operations. Incidence checks in the explicitly supplied approval types are also polynomial-time operations.
No expansion into an explicit voter list is needed, so the proof directly addresses the binary-rational support input.
The output fully resolves the assigned question. Its observation that unequal approval masses are unnecessary is consistent with the proof and does not change the requested input scope.
No additional clarification, lemma, 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.