Answer: Exactly computable in time polynomial in \(m,\tau,L\) for every fixed \(t\ge 3\); the budget decision problem belongs to \(\mathrm{P}\).
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any fixed 𝑡≥3, 𝑡-approval-TNC is NP-hard. To show this, we will focus on the following variant of the exact cover by 3-sets (X3C) problem; for some positive integer 𝑞, its input is a set 𝑈= {𝑢1, . . . ,𝑢3𝑞} of items, and a collection S = {𝑆1, . . . ,𝑆3𝑞} of subsets of 𝑈, where each subset has size 3 and where each item appears in exactly 3 subsets in S (this explains why the size of S is 3𝑞 as well). The goal is to find an exact cover S′ ⊆S of 𝑈, i.e., a subset S′ such that each item is covered exactly once. Notice that it necessarily holds that |S′| = 𝑞.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For fixed \(t\ge3\), given \(m\) candidates, a target \(p\), and a society supported on \(\tau\) complete rankings \(r_i\) with rational masses \(\mu_i\), what is the minimum total mass-weighted number of demotion operations needed to make \(p\) a co-winner under \(t\)-approval, when each ranking type's mass may be split among campaign outcomes? Equivalently, choose masses \(y_{i,S}\ge0\) ending with each size-\(t\) approval set \(S\), minimize \(\sum_{i,S}\kappa_i(S)y_{i,S}\), and require \(\sum_{i,S}y_{i,S}(\mathbf{1}[p\in S]-\mathbf{1}[c\in S])\ge0\) for every \(c\ne p\), where \(\sum_S y_{i,S}=\mu_i\) and \(\kappa_i(S)=\rho_i(w_i(S))-t\) for the least-preferred member \(w_i(S)\) of \(S\) in \(r_i\).
Fix an integer \(t\ge3\). Let \(C\) contain \(m>t\) candidates, including a preferred candidate \(p\).
A society is given by its support: a list of \(\tau\ge1\) distinct strict complete rankings \(r_i\), each with positive binary-rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(\rho_i(c)\) be the position of \(c\) in \(r_i\), with position \(1\) best.
A demotion operation moves any candidate downward by a positive integer number of positions in the current ranking, preserving the relative order of the other candidates. Each operation costs one per unit mass, independently of its distance; operations act sequentially, and each type's mass may be split among different operation sequences.
For every \(S\subseteq C\) with \(|S|=t\), define \(\kappa_i(S)=\max_{c\in S}\rho_i(c)-t\), the minimum number of operations making \(S\) the top approval set of type \(i\).
Choose real masses \(y_{i,S}\ge0\) with \(\sum_{S:|S|=t}y_{i,S}=\mu_i\), and minimize \(\sum_i\sum_{S:|S|=t}\kappa_i(S)y_{i,S}\).
Under \(t\)-approval, require \(p\) to be a co-winner: \(\sum_i\sum_{S:|S|=t}y_{i,S}(\mathbf{1}[p\in S]-\mathbf{1}[c\in S])\ge0\) for every \(c\ne p\); ties count as wins.
For each fixed \(t\ge3\), can this minimum be computed exactly in time polynomial in \(m,\tau,L\), or is deciding whether it is at most a given nonnegative binary-rational budget \(B\) NP-hard? Here \(L\) is the total input bit length, including \(B\) in the decision version.
For finite lists of indivisible voters, unit-cost constructive demotion campaigning under \(t\)-approval is NP-hard for every fixed \(t\ge3\), and admits a polynomial-time \(\min\{t,m-t\}\)-approximation ([source](https://doi.org/10.1613/jair.1.21371)).
No prior result settling this exact mass-splitting problem was located in the literature search.
For every fixed \(t\ge 3\), the minimum is exactly computable in time polynomial in \(m,\tau,L\). Consequently, the budget decision problem belongs to \(\mathrm{P}\).
The decisive facts are that mass splitting permits real-valued linear-programming variables and that, for fixed \(t\), there are only polynomially many possible approval sets.
Fix a ranking \(r_i\) and a set \(S\) of size \(t\). Write \(q=\max_{c\in S}\rho_i(c)\), and let \(s\in S\) occupy position \(q\).
Among the first \(q\) candidates, exactly \(q-t\) lie outside \(S\). Each such candidate \(x\) initially precedes \(s\), but must follow \(s\) once \(S\) occupies the top \(t\) positions.
An operation on a candidate other than \(x\) or \(s\) preserves their relative order. Demoting \(s\) cannot change their order from \(x\) preceding \(s\) to \(s\) preceding \(x\). Thus each of those \(q-t\) candidates must itself be demoted at least once. This proves the lower bound \(q-t\).
For the matching upper bound, demote each of those candidates to the bottom, once each. At its operation, each still precedes \(s\), so the demotion has positive distance. Afterward, the first \(t\) candidates are precisely \(S\). Hence the minimum operation count is \(\kappa_i(S)=q-t\).
Therefore any campaign inducing masses \(y_{i,S}\) costs at least \(\sum_{i,S}\kappa_i(S)y_{i,S}\). Conversely, any such masses can be realized at exactly that cost: split type \(i\) into portions of mass \(y_{i,S}\), and apply the construction above to each portion. No information about the final ranking beyond its approval set is needed.
Define \(\mathcal S_t=\{S\subseteq C:|S|=t\}\) and \(N=\tau\binom{m}{t}\). Introduce one variable \(y_{i,S}\) for each type \(i\) and set \(S\in\mathcal S_t\).
Minimize the linear objective
\(\displaystyle \sum_{i=1}^{\tau}\sum_{S\in\mathcal S_t}\kappa_i(S)y_{i,S}\)
subject to the following constraints:
The second family preserves each type’s mass. In the third family, the left-hand side is exactly \(p\)’s approval score minus \(c\)’s approval score. Thus these constraints impose precisely the required co-winner condition. Section 1 establishes that the objective also agrees exactly with campaign cost.
The feasible region is nonempty. Choose any \(S_0\in\mathcal S_t\) containing \(p\), and assign \(y_{i,S_0}=\mu_i\), with all other variables zero. Then \(p\) scores \(1\); every other candidate scores either \(1\) or \(0\).
Furthermore, nonnegativity and mass conservation give \(0\le y_{i,S}\le\mu_i\le 1\). The feasible region is therefore closed and bounded. Since \(0\le\kappa_i(S)\le m-t\) and the total mass is \(1\), the objective lies between \(0\) and \(m-t\). In particular, its minimum exists.
Because \(t\) is fixed, \(N=\tau\binom{m}{t}\le\tau m^t\) is polynomial in \(m,\tau\).
The inverse position tables \(\rho_i(c)\) can be constructed from the rankings in polynomial time. Enumerating every \(S\in\mathcal S_t\) then allows each coefficient \(\kappa_i(S)\) to be computed by taking a maximum over \(t\) positions.
After replacing each mass equality by two inequalities, the program has \(N+2\tau+m-1\) inequality rows. Its constraint coefficients belong to \(\{-1,0,1\}\); its objective coefficients are integers between \(0\) and \(m-t\); and its right-hand sides are zero or signed copies of the input rationals \(\mu_i\). Even a dense encoding consequently has total bit length polynomial in \(m,\tau,L\).
We now apply the standard rational linear-programming theorem: a linear program with explicitly encoded rational coefficients can be solved in time polynomial in its total binary encoding length, obtaining an exact rational optimum when feasible and bounded. This is a bit-complexity guarantee, including exact recovery, rather than merely numerical approximation; see [Trevisan’s linear-programming notes, Sections 2.4–2.5](https://lucatrevisan.wordpress.com/2011/01/24/cs261-lecture-5-linear-programming/).
All hypotheses hold here: the coefficients are rational, the explicit encoding has polynomial length, and the program is feasible and bounded. Thus its exact optimal value, and an optimal rational allocation, can be computed in the required time.
For the decision version, append the single rational constraint \(\sum_{i,S}\kappa_i(S)y_{i,S}\le B\). Because the minimum is attained, this augmented program is feasible exactly when the minimum is at most \(B\). Its encoding remains polynomial, so rational LP feasibility decides the question in polynomial time, including equality with the budget.
For indivisible voters, allocating an individual voter to approval sets requires a discrete choice. The present problem expressly permits splitting each type’s mass, so no integrality constraint applies to \(y_{i,S}\). The polynomial-size linear program solves exactly the stated mass-splitting problem; the supplied hardness result for indivisible voters does not transfer.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The explicit LP has polynomial size for every fixed \(t\), models the permitted mass splitting exactly, and satisfies the hypotheses of the stated rational linear-programming theorem. No major or minor mathematical issues were found.
Fix a type \(i\) and a set \(S\) with \(|S|=t\). The definitions of \(q=\max_{c\in S}\rho_i(c)\) and the candidate \(s\in S\) at position \(q\) are valid because the ranking is strict and complete.
Lower bound. All \(t\) members of \(S\) occur among the first \(q\) positions, so exactly \(q-t\) candidates in those positions lie outside \(S\). Each such candidate \(x\) precedes \(s\) initially and must follow \(s\) finally.
The relative-order argument is correct:
Since each operation moves only one candidate, the \(q-t\) distinct candidates require at least \(q-t\) operations. Sequential operations do not invalidate this argument.
Upper bound. Demoting each of these candidates to the bottom once is legal. Before its operation, each unprocessed candidate still precedes \(s\), since operations on other candidates preserve their relative order. Thus every prescribed demotion has positive distance.
After these operations, the remaining candidates from the original first \(q\) positions are exactly \(S\), and they precede all other candidates. Therefore the top approval set is \(S\), with precisely \(q-t\) operations.
The boundary case \(q=t\) is also covered: \(S\) is already the top approval set, and the construction performs zero operations.
Mass interpretation. The lower bound applies separately to every portion receiving an operation sequence. Conversely, arbitrary permitted masses \(y_{i,S}\) can be assigned the corresponding constructions. Hence the weighted objective agrees exactly with the minimum campaign cost for those allocations.
The variables range over precisely the type–approval-set pairs allowed by the task.
Nonnegativity and the equations \(\sum_S y_{i,S}=\mu_i\) encode an arbitrary split of each type’s mass. There is no unjustified integrality restriction.
For each competitor \(c\), the coefficient \(\mathbf 1[p\in S]-\mathbf 1[c\in S]\) gives the contribution to the difference between the approval scores of \(p\) and \(c\). Requiring this difference to be nonnegative correctly implements co-winning, including ties.
The objective uses the verified costs \(\kappa_i(S)\). Thus both feasibility and cost match the assigned problem.
A set \(S_0\) of size \(t\) containing \(p\) exists because \(m>t\). Assigning every type entirely to \(S_0\) gives \(p\) score \(1\), with every competitor scoring either \(1\) or \(0\). This proves feasibility.
Every variable satisfies \(0\le y_{i,S}\le\mu_i\le1\). The feasible region is closed and bounded in a finite-dimensional space, so the linear objective attains its minimum.
The objective bounds are also correct: \(t\le q\le m\) implies \(0\le\kappa_i(S)\le m-t\), and the allocated masses sum to \(1\).
For fixed \(t\), the variable count \(N=\tau\binom mt\le\tau m^t\) is polynomial in the specified parameters. Position tables, approval sets, and objective coefficients can all be constructed in polynomial time.
The inequality count \(N+2\tau+m-1\) correctly includes nonnegativity, two inequalities per mass equality, and one score constraint per competitor. The stated coefficient ranges and rational right-hand sides are correct. Even dense storage has polynomial total encoding length.
The prover states the required theorem precisely: explicitly encoded rational LPs admit polynomial-time exact optimization when feasible and bounded. The cited [Trevisan notes, Sections 2.4–2.5](https://lucatrevisan.wordpress.com/2011/01/24/cs261-lecture-5-linear-programming/) support polynomial bit complexity and exact rational solution recovery. All necessary hypotheses are verified here; the mass equalities do not require a full-dimensional feasible region.
Adding the objective constraint with right-hand side \(B\) preserves polynomial encoding length. Because the minimum is attained, augmented feasibility is equivalent to the minimum being at most \(B\), including equality and \(B=0\).
The distinction from indivisible voters is valid: the task expressly permits continuous allocation. The supplied discrete hardness result therefore does not contradict this LP algorithm.
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.