Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 3 — class: hardness
Given candidates \(C\) partitioned into parties \(P_1,\ldots,P_t\), target party \(P_w\), a societal axis \(B\), and rational masses \(\mu_\rho\) over complete rankings \(\rho\) that are single-peaked with respect to \(B\), decide whether there exists \(q\in P_1\times\cdots\times P_t\) such that some \(q_w\) maximizes \(\operatorname{score}_{\mu,q}(c)=\sum_{\rho\in T:\,c\text{ is top-ranked among }q\text{ under }\rho}\mu_\rho\), with ties accepted.
Let \(C\) contain \(m\geq 1\) candidates, partitioned into \(t\geq 1\) nonempty parties \(P_1,\ldots,P_t\), with target index \(1\leq w\leq t\). A supplied societal axis \(B\) is a linear order on \(C\); party members need not be consecutive on it.
A society is given by its support \(T\): a list of \(\tau\geq 1\) distinct strict complete rankings of \(C\), each single-peaked with respect to \(B\), with positive binary rational masses \(\mu_\rho\) satisfying \(\sum_{\rho\in T}\mu_\rho=1\). Here \(\tau=|T|\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L,t\).
Each party nominates exactly one candidate: \(q=(q_1,\ldots,q_t)\in\prod_{i=1}^{t}P_i\). Writing \(Q=\{q_1,\ldots,q_t\}\), define \(s_{\mu,q}(c)=\sum_{\rho\in T:\,c\text{ is highest in }Q\text{ under }\rho}\mu_\rho\) for \(c\in Q\). The decision problem asks whether some nomination satisfies \(s_{\mu,q}(q_w)\geq s_{\mu,q}(q_i)\) for every \(1\leq i\leq t\); ties count as wins.
Is this decision problem solvable in polynomial time in \(m,\tau,L,t\), or is it NP-hard?
For explicit finite electorates, the same nomination problem is NP-complete with single-peaked rankings, and is in \(\mathrm{P}\) when every party is consecutive on the supplied axis. [Source](https://www.lamsade.dauphine.fr/~lang/papers/FGLLM16.pdf)
No published result specifically treating the stated rational-mass support representation was located.
The decision problem is \(\mathrm{NP}\)-complete. Consequently, it has a polynomial-time algorithm in \(m,\tau,L,t\) only if \(\mathrm{P}=\mathrm{NP}\).
For \(t=1\), the answer is always yes. The hardness result concerns the general case where \(t\) is part of the input.
We use the following established result: for an explicitly listed finite electorate with strict single-peaked rankings, deciding whether some nomination makes the target party’s nominee a plurality winner is \(\mathrm{NP}\)-complete. This is Theorem 3 of [Faliszewski et al., *How Hard Is It for a Party to Nominate an Election Winner?*](https://www.lamsade.dauphine.fr/~lang/papers/FGLLM16.pdf). Their model counts ties as wins, and their hardness construction explicitly supplies a societal axis. Thus its axis can be included in the source instance.
Let a source instance have \(n\geq 1\) explicitly listed voters, with rankings \(\rho_1,\ldots,\rho_n\). Keep its candidates, parties, target index, and axis unchanged.
Let \(T\) be the set of distinct rankings occurring in this list. For each \(\rho\in T\), define
\[ k_\rho=\left|\{j:\rho_j=\rho\}\right|, \qquad \mu_\rho=\frac{k_\rho}{n}. \]
The resulting instance satisfies all required hypotheses:
This transformation is polynomial in the source input length. Identical rankings can be grouped by sorting their explicitly supplied encodings. Each numerator and denominator needs \(O(\log(n+1))\) bits; reducing fractions, if required by the encoding, also takes polynomial time. No unlisted rankings are generated.
For any nomination \(q\) and any \(c\in Q\), let \(v_q(c)\) be the number of source voters whose highest-ranked nominee is \(c\). Grouping these voters by ranking gives
\[ s_{\mu,q}(c) = \sum_{\rho\in T:\,c\text{ is highest in }Q\text{ under }\rho} \frac{k_\rho}{n} = \frac{v_q(c)}{n}. \]
Because \(n>0\), for every party index \(i\),
\[ s_{\mu,q}(q_w)\geq s_{\mu,q}(q_i) \quad\Longleftrightarrow\quad v_q(q_w)\geq v_q(q_i). \]
Thus the transformation preserves the winning nominations exactly, including ties. It is a polynomial many-one reduction from the established \(\mathrm{NP}\)-hard problem, proving \(\mathrm{NP}\)-hardness of the rational-mass support problem.
A certificate specifies one candidate \(q_i\in P_i\) for each party. Its encoding has \(O(t\log(m+1))\) bits.
Write each input mass as \(\mu_\rho=a_\rho/b_\rho\), with positive binary integers \(a_\rho,b_\rho\). Define
\[ D=\prod_{\rho\in T}b_\rho, \qquad A_\rho=a_\rho\frac{D}{b_\rho}. \]
Each \(A_\rho\) is a positive integer, and normalization implies
\[ \sum_{\rho\in T}A_\rho = D\sum_{\rho\in T}\mu_\rho = D. \]
The bit length of \(D\) is at most \(1+\sum_{\rho\in T}\log_2 b_\rho\), hence \(O(L)\). Every \(A_\rho\), and every partial sum of these integers, is at most \(D\), so all score computations use \(O(L)\)-bit integers.
After checking that each certificate candidate belongs to its designated party, scan each supported ranking from highest to lowest until encountering a nominee. Add \(A_\rho\) to that nominee’s integer score. The resulting score is
\[ S_q(c)=D\,s_{\mu,q}(c). \]
Accept precisely when \(S_q(q_w)\geq S_q(q_i)\) for every \(i\). Since \(D>0\), this is exactly the required condition.
Using schoolbook integer multiplication and division, a conservative bound for verification on the stated valid inputs is \(O((\tau m+\tau+t+1)L^2)\) bit operations. This includes scanning the rankings, forming the integer weights, accumulating scores, and comparing them. It is polynomial in \(m,\tau,L,t\), proving membership in \(\mathrm{NP}\).
The polynomial reduction and polynomial certificate verification together prove \(\mathrm{NP}\)-completeness. A separate published hardness theorem for rational-mass supports is unnecessary: grouping an explicit electorate preserves every nomination outcome and produces a polynomial-size instance of the stated representation.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the assigned problem: the rational-mass support representation yields an \(\mathrm{NP}\)-complete decision problem. I found no major or minor mathematical issues.
Theorem 3 of the cited paper states that Plurality-POSSIBLE PRESIDENT is \(\mathrm{NP}\)-complete even for single-peaked preferences. Its definitions require disjoint parties, exactly one nominee per party, and preferences over all candidates. The paper explicitly uses the nonunique-winner convention, so ties count as wins. Its single-peakedness discussion assumes an available axis, and the hardness construction explicitly defines that axis. Thus the prover’s invocation establishes hardness with a supplied axis and without requiring consecutive parties. The construction also has a nonempty electorate. [Source: definitions and Theorem 3](https://www.lamsade.dauphine.fr/~lang/papers/FGLLM16.pdf).
The prover states the external result sufficiently precisely and correctly checks the model features relevant to its application. No additional theorem is needed to transfer hardness to the new representation.
Grouping identical source rankings gives a support of distinct strict complete rankings. Keeping the same axis preserves single-peakedness.
For every supported ranking, its multiplicity satisfies \(1\leq k_\rho\leq n\), so \(\mu_\rho=k_\rho/n\) is positive. Every source voter belongs to exactly one multiplicity group, giving \(\sum_{\rho\in T}k_\rho=n\) and hence the claimed normalization.
The support-size bound \(1\leq\tau\leq n\) is correct. The candidate partition, party nonemptiness, and target-index restriction are inherited from the source instance.
Since the voters are explicitly listed, grouping their ranking encodings by sorting is polynomial in that input length. Both integers in each output fraction are at most \(n\), so their binary encodings have \(O(\log(n+1))\) bits.
There are at most \(n\) output rankings, and the remaining instance components are copied. Thus the transformation has polynomial output size and polynomial computation time. Optional fraction reduction does not change this conclusion.
The argument correctly uses the number of explicitly listed source voters here; it does not confuse the target support size with the number of possible rankings.
Fix any nomination \(q\). Every strict complete ranking has exactly one highest-ranked nominee because the nominee set is nonempty.
Grouping voters with identical rankings therefore gives exactly \(s_{\mu,q}(c)=v_q(c)/n\) for each nominee \(c\). Because \(n>0\), dividing all source scores by \(n\) preserves every weak score comparison.
The candidate and party sets are unchanged, so the feasible nominations are identical in the two instances. The displayed equivalence consequently holds for every nomination and every competing party, preserving both yes and no instances, including tied victories. This establishes a polynomial many-one reduction.
One candidate identifier per party has the stated \(O(t\log(m+1))\) certificate length. Checking membership in each designated party ensures a valid nomination; disjointness of the parties ensures distinct nominees.
The product \(D=\prod_{\rho\in T}b_\rho\) is positive and divisible by every denominator. Its bit length is \(O(L)\), as claimed. Consequently, every \(A_\rho=a_\rho(D/b_\rho)\) is an integer.
On the stipulated valid inputs, normalization gives \(\sum_{\rho\in T}A_\rho=D\). Positivity then ensures that each weight and every score accumulator is at most \(D\). Thus exact score calculations require only \(O(L)\)-bit integers.
Scanning each ranking to its first nominee assigns its entire weight to precisely the correct candidate. The resulting identity \(S_q(c)=D\,s_{\mu,q}(c)\), followed by comparisons using \(D>0\), verifies exactly the target winning condition.
Schoolbook multiplication and division on \(O(L)\)-bit integers cost \(O(L^2)\) per operation. Forming the common denominator and weights requires \(O(\tau)\) such operations. Ranking scans, score additions, party-membership checks, and final comparisons fit within the conservative bound \(O((\tau m+\tau+t+1)L^2)\).
The argument expressly applies to the valid inputs specified by the task. No input-validation assumption breaks its membership claim.
For \(t=1\), the sole nominee receives all mass and wins. This also covers \(m=1\), since a partition into nonempty parties then forces \(t=1\). The construction and verifier remain valid when \(\tau=1\).
Repair feedback: None required. The reduction establishes hardness, and the verifier establishes membership in \(\mathrm{NP}\); together they justify the claimed classification.
⟨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.