Answer: Polynomial-time solvable: \(\mathrm P\), with running time \(\operatorname{poly}(m,\tau,L)\).
Theorem 4.10 — class: hardness
Given \(m\) candidates, a scoring rule \(f\), a target \(p\), and a finite support of rankings \(\pi\) with binary-rational registered and eligible masses \(r_\pi,u_\pi\), normalized so that \(\sum_\pi(r_\pi+u_\pi)=1\), decide whether there are rational mobilized masses \(x_\pi\) and a budget \(\kappa\) such that \(0\le x_\pi\le u_\pi\), \(\sum_\pi x_\pi\le\kappa\), and \(\sum_\pi(r_\pi+x_\pi)(\alpha^{f,m}_{\operatorname{pos}_\pi(p)}-\alpha^{f,m}_{\operatorname{pos}_\pi(c)})\ge0\) for every candidate \(c\).
Fix a pure scoring generator \(f\) that computes, in time polynomial in \(m\), a nonincreasing vector \(\alpha^{f,m}\in\mathbb Q^m\); deleting one entry of \(\alpha^{f,m}\) gives \(\alpha^{f,m-1}\). Assume \(\alpha^{f,m_0}_4>\alpha^{f,m_0}_{m_0-2}\) for some \(m_0\ge7\).
An instance has a candidate set \(C\) of size \(m\ge1\), a target \(p\in C\), and an input budget \(\kappa\in\mathbb Q\cap[0,1]\).
A society is given by its support: a list of \(\tau\) strict rankings \(\pi\) of \(C\), each with binary-rational registered and eligible masses \(r_\pi,u_\pi\ge0\), where \(r_\pi+u_\pi>0\) and \(\sum_\pi(r_\pi+u_\pi)=1\). Thus \(\tau\) is the support size, not the number of possible rankings.
Eligible mass may be mobilized in rational portions at unit cost per unit mass; registered mass remains present. Ties count as wins for \(p\).
Decide whether there exist \(x_\pi\in\mathbb Q\) satisfying \(0\le x_\pi\le u_\pi\), \(\sum_\pi x_\pi\le\kappa\), and \(\sum_\pi(r_\pi+x_\pi)(\alpha^{f,m}_{\operatorname{pos}_\pi(p)}-\alpha^{f,m}_{\operatorname{pos}_\pi(c)})\ge0\) for every \(c\in C\), where \(\operatorname{pos}_\pi(c)\) is the position of \(c\) in \(\pi\).
Let \(L\) be the total bit length of the masses, budget, and scoring coefficients; state running times in \(m,\tau,L\).
For each such fixed \(f\), is this continuous constructive control problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
Discrete constructive control by adding at most a given number of unweighted voters is NP-complete for every fixed generator satisfying the stated conditions. [Verified source](https://arxiv.org/pdf/1404.4560v1)
No result settling exactly this continuous problem was located in the literature search.
The continuous problem is solvable in time polynomial in \(m,\tau,L\) for every fixed generator in the question. In fact, the proof applies to any polynomial-time computable rational scoring vectors; purity and the stated score gap are unnecessary.
Enumerate the supplied rankings as \(\pi_1,\ldots,\pi_\tau\), and write their masses as \(r_i,u_i\). Set \(\alpha=\alpha^{f,m}\). For each opponent \(c\in C\setminus\{p\}\), define
\(\displaystyle d_{ci}=\alpha_{\operatorname{pos}_{\pi_i}(p)}-\alpha_{\operatorname{pos}_{\pi_i}(c)},\qquad b_c=-\sum_{i=1}^{\tau}r_i d_{ci}.\)
Consider the real polyhedron \(P\subseteq\mathbb R^\tau\) defined by
\(\displaystyle 0\le x_i\le u_i\quad(1\le i\le\tau),\)
\(\displaystyle \sum_{i=1}^{\tau}x_i\le\kappa,\)
\(\displaystyle \sum_{i=1}^{\tau}d_{ci}x_i\ge b_c\quad(c\in C\setminus\{p\}).\)
There are \(\tau\) variables and \(2\tau+m\) inequalities.
For each opponent \(c\), its inequality is equivalent to
\(\displaystyle \sum_{i=1}^{\tau}(r_i+x_i)\bigl(\alpha_{\operatorname{pos}_{\pi_i}(p)}-\alpha_{\operatorname{pos}_{\pi_i}(c)}\bigr)\ge0.\)
Thus it states exactly that \(p\)'s score is at least \(c\)'s score. The omitted inequality for \(c=p\) is identically satisfied. The remaining inequalities express precisely the mobilization bounds and budget.
Consequently, the original instance is a yes-instance exactly when \(P\) contains a rational point. We next justify replacing rational feasibility by real feasibility.
Let \(D\) be the product of the positive denominators of all input masses, the budget, and the scoring coefficients, represented as binary fractions. Since their total encoding length is \(L\), we have \(D\le2^L\).
Every \(d_{ci}\) has denominator dividing \(D\). Every product \(r_i d_{ci}\), and hence every \(b_c\), has denominator dividing \(D^2\). Multiplying all inequalities by the positive integer \(D^2\) therefore gives an equivalent system with integer coefficients.
These integer coefficients have \(O(L)\) bits. Indeed, each scoring coefficient has absolute value at most \(2^L\), so
\(\displaystyle |d_{ci}|\le2^{L+1}.\)
The normalization and nonnegativity imply \(\sum_i r_i\le1\), giving
\(\displaystyle |b_c|\le\sum_i r_i|d_{ci}|\le2^{L+1}.\)
Also \(u_i,\kappa\in[0,1]\). After multiplication by \(D^2\), all matrix and right-hand-side entries consequently have absolute value at most \(2^{3L+1}\).
Suppose \(P\) is nonempty. It is closed and bounded because \(0\le x_i\le u_i\le1\), so it is compact. Obtain a point \(v\) by successively minimizing coordinates \(x_1,\ldots,x_\tau\), each time restricting to the preceding minimizers. Compactness ensures that every minimum exists, and the final set is a singleton.
This point is extreme: if \(v=(y+z)/2\) with \(y,z\in P\), minimality of the first coordinate forces \(y_1=z_1=v_1\). Successive minimality forces equality of every subsequent coordinate, so \(y=z=v\).
The active constraint normals at \(v\) span \(\mathbb R^\tau\). Otherwise, take a nonzero vector \(h\) orthogonal to all active normals. Active constraints remain equalities at \(v\pm\varepsilon h\). Each inactive constraint has positive slack, so, because there are finitely many constraints, sufficiently small \(\varepsilon>0\) preserves them all. Both points then belong to \(P\), contradicting extremality.
Choose \(\tau\) linearly independent active constraints from the integer system. They give \(Av=a\), where \(A\) is a nonsingular integer matrix. Cramer's rule yields
\(\displaystyle v_j=\frac{\det A_j}{\det A},\)
where \(A_j\) replaces column \(j\) by \(a\). Hence \(v\) is rational.
For completeness, if all entries are bounded by \(H=2^{3L+1}\), Hadamard's inequality gives
\(\displaystyle |\det A|,\ |\det A_j|\le(\sqrt{\tau}\,H)^\tau.\)
Thus each coordinate has numerator and denominator bit length \(O(\tau(L+\log(\tau+1)))\), and the entire witness has polynomial bit length.
We have proved that \(P\) is real-feasible if and only if it is rational-feasible.
Use the standard exact linear programming theorem: feasibility of an explicitly given integer linear inequality system can be decided in time polynomial in its binary encoding length, including when its feasible region has empty interior. This is the polynomial-time feasibility theorem for the ellipsoid method; see [MIT's linear programming lecture notes, slides 25–28](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
All hypotheses hold here: the integer system is explicit, has finitely many inequalities, and has polynomial encoding length. A sufficient bound for that length is
\(\displaystyle B=O\bigl((m+2\tau)(\tau+1)(L+\log(m+\tau+2))\bigr).\)
The algorithm computes the scoring vector, reads the supplied rankings to determine positions, constructs the integer system, and decides its feasibility. These construction steps take polynomial time in \(m,\tau,L\). If \(T_f(m)\) denotes the fixed generator's polynomial running time, the total running time is
\(\displaystyle T_f(m)+\operatorname{poly}\bigl(m\tau\log(m+1)+L+B\bigr)=\operatorname{poly}(m,\tau,L).\)
Only the \(\tau\) supplied rankings are used; no enumeration of all possible rankings occurs. Non-strict inequalities preserve ties exactly. For \(m=1\), choosing every \(x_i=0\) always succeeds.
The discrete problem restricts each mobilization amount to an integer voter count. Here rational portions are permitted, so the feasible set is the rational part of a polyhedron whose real feasibility is decidable in polynomial time. Discrete hardness therefore does not transfer merely by rescaling voter counts into masses: the rescaled continuous instance also admits fractional choices.
The requested classification is membership in \(\mathrm P\); NP-hardness under polynomial-time many-one reductions would therefore imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: the continuous control problem is solvable in time polynomial in \(m,\tau,L\). I found no mathematical errors or gaps requiring clarification.
The coefficients \(d_{ci}\) are precisely the score differences contributed by one unit of mass with ranking \(\pi_i\). Moving the registered contribution to the right-hand side gives \(b_c=-\sum_i r_i d_{ci}\), with the correct sign.
Thus each opponent constraint is equivalent to the corresponding winning condition in the task. The bounds and budget constraint also match exactly. Omitting \(c=p\) is valid because its score difference is identically zero.
The constraint count is correct: \(2\tau\) bounds, one budget inequality, and \(m-1\) opponent inequalities give \(2\tau+m\) inequalities.
Under the stated binary encoding, the product \(D\) of the positive input denominators satisfies \(D\le 2^L\). Each scoring coefficient and mass has denominator dividing \(D\).
Consequently, the denominator of each \(d_{ci}\) divides \(D\), and the denominator of each product \(r_i d_{ci}\) divides \(D^2\). Taking a finite sum preserves this latter divisibility, so multiplication by \(D^2\) makes every constraint coefficient and right-hand side integral.
The magnitude estimates also check out. The scoring coefficients have absolute value at most \(2^L\), hence \(|d_{ci}|\le 2^{L+1}\). Normalization gives \(\sum_i r_i\le 1\), which justifies \(|b_c|\le 2^{L+1}\). It also gives \(u_i\le 1\), while the task explicitly gives \(\kappa\le 1\). Therefore the claimed bound \(2^{3L+1}\) after scaling is sufficient, including for the bound and budget constraints.
The normalization condition implies \(\tau\ge 1\). The polyhedron is closed and bounded by its coordinate bounds, so a nonempty feasible region is compact.
Successive coordinate minimization is legitimate: each restricted minimizer set remains nonempty and compact. After all coordinates are fixed, it is a singleton. The midpoint argument correctly establishes extremality, including when the feasible region has empty interior.
The active-normal argument is also valid. If the active normals failed to span the ambient space, a nonzero orthogonal direction would preserve active equalities. Finitely many inactive constraints with positive slack permit sufficiently small perturbations in both directions. This contradicts extremality.
Selecting \(\tau\) independent active constraints therefore gives a nonsingular integer system determining the extreme point. Cramer’s rule proves that point is rational. Conversely, rational feasibility trivially implies real feasibility.
Every row of either determinant matrix has Euclidean norm at most \(\sqrt{\tau}\,H\), so the stated Hadamard bound applies to both \(A\) and each \(A_j\).
Because \(\det A\) is a nonzero integer, Cramer’s rule yields coordinate numerator and denominator lengths bounded by \(O(\tau(L+\log(\tau+1)))\). Reduction of the fractions cannot increase these lengths. The entire witness therefore has polynomial encoding length.
The prover states the required theorem precisely enough: feasibility of an explicitly encoded integer linear inequality system is decidable in polynomial time in its binary encoding length, including for feasible regions with empty interior. The cited [MIT lecture notes, slides 25–28](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf) explicitly address arbitrary polyhedra and conclude polynomial-time feasibility for integer data.
The constructed system satisfies these hypotheses. Its stated encoding bound \(B\) is a valid upper bound for the dense matrix, right-hand sides, and dimensional bookkeeping.
Reading rankings, constructing positions and coefficients, and performing the rational arithmetic and denominator scaling all require polynomial time in \(m,\tau,L\). Including \(T_f(m)\) correctly accounts for generating the scoring vector. The resulting runtime expression establishes the requested polynomial bound without enumerating rankings outside the supplied support.
Non-strict inequalities implement the stipulated treatment of ties. Zero eligible masses and zero budget are covered by the same formulation and feasibility theorem. For \(m=1\), the proposed zero mobilization is feasible.
Purity and the score-gap assumption are unused, which is consistent with the stronger claim made by the prover. The observation about discrete hardness is appropriately limited: allowing fractional choices prevents a direct transfer of the discrete result. The final statement about NP-hardness implying \(\mathrm P=\mathrm{NP}\) is correct under the specified reductions.
No repair or additional clarification 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.