Answer: polynomial-time solvable
Proposition 2 — class: algorithmic
Given candidates \(C\), a rational society \(\mu\) over complete rankings, and an integer resolution \(n\), define \(X^\mu_{i,c}=\sum_{\pi:\operatorname{pos}_\pi(c)=i}\mu_\pi\). Output ranking types with integer multiplicities summing to \(n\), minimizing \(\sum_{i,c}\lvert nX^\mu_{i,c}-p_{i,c}\rvert\) subject to \(\lvert nX^\mu_{i,c}-p_{i,c}\rvert\le 1\), where \(P=(p_{i,c})\) is the resulting position matrix.
Given a candidate set \(C\) with \(m\geq 1\), let \(\mathcal R(C)\) be the strict complete rankings of \(C\); \(\operatorname{pos}_\pi(c)\) is the position of \(c\), with the top position numbered \(1\).
A society is given by its support: the list of the \(\tau\) ranking types with positive mass, each mass a binary rational, with \(\sum_\pi\mu_\pi=1\). Here \(\tau\) is the support size, not \(m!\).
The resolution \(n\geq1\) is an integer encoded in binary; \(L\) is the total input bit length. Define \(X^\mu_{i,c}=\sum_{\pi:\operatorname{pos}_\pi(c)=i}\mu_\pi\).
Output a list of distinct rankings \(\rho\in\mathcal R(C)\) with positive binary integer multiplicities \(k_\rho\), summing to \(n\); output rankings need not belong to the input support. Their position matrix is \(p_{i,c}=\sum_{\rho:\operatorname{pos}_\rho(c)=i}k_\rho\).
Minimize \(\sum_{i=1}^{m}\sum_{c\in C}|nX^\mu_{i,c}-p_{i,c}|\), subject to \(|nX^\mu_{i,c}-p_{i,c}|\leq1\) for every position and candidate. Any minimizer is acceptable.
Is this optimization problem solvable in time polynomial in \(m,\tau,L\), including \(\log n\), or is it NP-hard?
Known results: arbitrary bistochastic matrix input admits polynomial-time election recovery with exactly these error constraints and objective; integer position matrices admit recovery using at most \(m^2-2m+2\) distinct rankings. [Verified source](https://arxiv.org/pdf/2105.07815).
These results already cover the stated distribution-input problem; its requested complexity target is therefore not open.
The problem is solvable in time polynomial in \(m,\tau,L\), including \(\log n\), with the requested compressed output.
The cited paper’s Proposition 2 states the corresponding optimization result for bistochastic matrix inputs, and Proposition 1 provides recovery with at most \(m^2-2m+2\) distinct rankings. [Boehmer et al., *Putting a Compass on the Map of Elections*, Section 3 and Appendix A](https://arxiv.org/pdf/2105.07815).
Below is a direct proof that explicitly handles binary encoding and all integer values permitted by the error constraints.
Write \(X=X^\mu\) and \(a_{i,c}=nX_{i,c}\). Each input ranking places exactly one candidate in each position and places each candidate exactly once. Therefore,
\[ \sum_{c\in C}X_{i,c}=1,\qquad \sum_{i=1}^{m}X_{i,c}=1,\qquad X_{i,c}\geq 0. \]
Consequently, every row and column of \(A=(a_{i,c})\) sums to \(n\).
For exact arithmetic, write each input mass as \(\mu_\pi=v_\pi/d_\pi\), and take \(Q=\prod_\pi d_\pi\). The bit length of \(Q\) is at most the sum of the input denominator bit lengths, hence is \(O(L)\). Every entry of \(X\) can be computed with denominator \(Q\), and every entry of \(A\) has numerator at most \(nQ\). Thus computing \(A\) takes polynomial time, with intermediate bit lengths polynomial in \(L\).
Any permitted output induces a nonnegative integer matrix \(P\) whose rows and columns sum to \(n\). Section 3 proves the converse constructively. It therefore suffices to optimize over such matrices.
For each entry, define
\[ \ell_{i,c}=\max\{0,\lceil a_{i,c}-1\rceil\}, \qquad u_{i,c}=\lfloor a_{i,c}+1\rfloor, \qquad w_{i,c}=u_{i,c}-\ell_{i,c}. \]
These are exactly the bounds for a nonnegative integer entry satisfying \(|a_{i,c}-p_{i,c}|\leq 1\). Moreover,
\[ \ell_{i,c}\leq a_{i,c}\leq u_{i,c}, \qquad 0\leq a_{i,c}-\ell_{i,c}\leq 1, \qquad w_{i,c}\leq 2. \]
In particular, these bounds retain both possible deviations at entries where \(a_{i,c}\) is integral.
Define integer residual margins
\[ r_i=n-\sum_{c\in C}\ell_{i,c}, \qquad s_c=n-\sum_{i=1}^{m}\ell_{i,c}. \]
Using the margins of \(A\), we obtain
\[ r_i=\sum_{c\in C}(a_{i,c}-\ell_{i,c}), \qquad s_c=\sum_{i=1}^{m}(a_{i,c}-\ell_{i,c}). \]
Hence \(0\leq r_i,s_c\leq m\), and
\[ B:=\sum_{i=1}^{m}r_i=\sum_{c\in C}s_c\leq m^2. \]
Construct a directed network with a source, one vertex for each position, one vertex for each candidate, and a sink:
\[ \gamma_{i,c,j} = |a_{i,c}-(\ell_{i,c}+j)| - |a_{i,c}-(\ell_{i,c}+j-1)|. \]
We seek a minimum-cost flow of value \(B\).
Feasibility. The quantities \(d_{i,c}=a_{i,c}-\ell_{i,c}\) have row sums \(r_i\), column sums \(s_c\), and satisfy \(0\leq d_{i,c}\leq w_{i,c}\). Distributing \(d_{i,c}\) over the corresponding unit-capacity arcs gives a feasible fractional flow of value \(B\).
We use the standard minimum-cost-flow theorem: with integer capacities and a prescribed integer flow value, fractional feasibility implies the existence of an integral minimum-cost flow; an optimum can be computed in time polynomial in the network size and the bit lengths of capacities and rational costs. All its hypotheses hold here.
Exact correspondence with the objective. Since absolute value is convex, the incremental costs satisfy \(\gamma_{i,c,1}\leq\gamma_{i,c,2}\) whenever both arcs exist. Thus an integral optimum can be chosen to use the first \(t_{i,c}\) parallel arcs for every pair: replacing a used later arc by an unused earlier arc preserves feasibility and cannot increase cost.
Set \(p_{i,c}=\ell_{i,c}+t_{i,c}\). Because the total source capacity and total sink capacity both equal \(B\), a flow of value \(B\) saturates those arcs. Consequently, \(P\) has every row and column sum equal to \(n\). Its entries satisfy the required bounds.
The costs telescope:
\[ \sum_{j=1}^{t_{i,c}}\gamma_{i,c,j} = |a_{i,c}-p_{i,c}|-|a_{i,c}-\ell_{i,c}|. \]
Conversely, every feasible integer matrix \(P\) defines such a prefix flow by setting \(t_{i,c}=p_{i,c}-\ell_{i,c}\). Therefore minimum flow cost equals the minimum requested objective minus the fixed constant \(\sum_{i,c}|a_{i,c}-\ell_{i,c}|\). The recovered matrix is globally optimal.
Bit complexity. The network has \(2m+2\) vertices and at most \(2m^2+2m\) arcs. Its required flow value is at most \(m^2\), independently of \(n\). Each cost has denominator dividing \(Q\) and absolute value at most one, by the triangle inequality. Multiplying all costs by \(Q\) produces integer costs of \(O(L)\) bits without changing the optimum. Thus this optimization takes polynomial time in the specified parameters.
Let \(R=P\). Maintain the invariant that \(R\) is nonnegative and integral, with every row and column summing to a common integer \(N\), initially \(N=n\).
When \(N>0\), form the bipartite graph whose vertices are positions and candidates, with edge \((i,c)\) exactly when \(R_{i,c}>0\).
For any set \(S\) of position vertices, let \(\Gamma(S)\) be its candidate neighbors. All mass in the rows of \(S\) lies in columns \(\Gamma(S)\). Therefore,
\[ N|S| = \sum_{i\in S}\sum_{c\in\Gamma(S)}R_{i,c} \leq \sum_{c\in\Gamma(S)}\sum_{i=1}^{m}R_{i,c} = N|\Gamma(S)|. \]
Since \(N>0\), Hall’s condition holds. Hall’s theorem gives a perfect matching \(M\), which defines a ranking \(\rho\): candidate \(c\) occupies position \(i\) precisely when \((i,c)\in M\).
Let
\[ k=\min_{(i,c)\in M}R_{i,c}. \]
Record \(\rho\) with multiplicity \(k\), and subtract \(k\) from every matched entry. Here \(k\) is a positive integer; the new matrix remains nonnegative and integral, and its common margin becomes \(N-k\).
At least one positive entry becomes zero in every iteration, and no zero entry ever becomes positive. Hence there are at most \(m^2\) iterations. Furthermore, a recorded matching cannot recur: one of its edges becomes permanently zero when it is recorded. Thus the recorded rankings are distinct.
Upon termination, \(R=0\). Since each iteration decreases the common margin by its recorded multiplicity, the multiplicities sum to \(n\). The resulting rankings reproduce \(P\) exactly and therefore attain the optimum.
Each matching is computable in polynomial time. Every multiplicity is at most \(n\) and needs \(O(\log(n+1))\) bits. The total output length is
\[ O\!\left(m^2\bigl(m\log(m+1)+\log(n+1)\bigr)\right). \]
This establishes polynomial running time and polynomial output length even when \(n\) is encoded in binary.
The distribution-to-matrix computation, exact optimization, and compressed ranking recovery all run in polynomial time in \(m,\tau,L\). They apply to every \(m\geq 1\) and \(n\geq 1\), and they do not require output rankings to belong to the input support.
⟨structured verdict parsed — rendered above⟩
The output proves the requested polynomial-time classification. The direct argument correctly optimizes over all permitted integer position matrices and recovers distinct rankings with binary multiplicities in polynomial time. I found no major or minor mathematical issues.
The output addresses the actual input representation: a support list of size \(\tau\), rational masses, and binary-encoded \(n\). It also handles the required compressed output and allows rankings outside the input support.
The citations are accurate. Proposition 2 states the entrywise error constraint and the same absolute-error minimization objective; Proposition 1 states recovery with at most \(m^2-2m+2\) distinct rankings. [Boehmer et al., Section 3 and Appendix A](https://arxiv.org/pdf/2105.07815).
The direct proof establishes binary bit complexity independently of any encoding conventions in those propositions. Its weaker recovery bound of \(m^2\) rankings is sufficient for USER_TASK.
Every supported ranking contributes exactly once to each position and exactly once for each candidate. Together with the normalization of the masses, this establishes nonnegativity and all row and column sums of \(X\).
The common denominator \(Q=\prod_\pi d_\pi\) has bit length bounded by the sum of the denominator bit lengths. Because the masses are positive and sum to one, each entry of \(X\) lies in \([0,1]\), and an entry of \(A=nX\), represented over denominator \(Q\), has numerator at most \(nQ\). Since the encoding of \(n\) is included in \(L\), the claimed polynomial arithmetic bounds hold.
The reduction to nonnegative integer matrices with margins \(n\) is valid: every output induces such a matrix, and Section 3 constructively establishes the converse.
The definitions of \(\ell_{i,c}\) and \(u_{i,c}\) exactly describe the nonnegative integers satisfying the error constraint.
The asserted bounds hold in every case:
Thus \(0\leq a_{i,c}-\ell_{i,c}\leq1\) and \(w_{i,c}\leq2\). In particular, the construction correctly retains the additional permitted choices at integral entries.
The residual margins are integers, are nonnegative, and are at most \(m\). Their totals agree because the original row and column totals agree. Consequently, \(B\leq m^2\) is correct.
The proposed fractional flow is feasible. Each \(d_{i,c}\) can be distributed among its \(w_{i,c}\) unit-capacity arcs, and its row and column sums are exactly the residual margins.
The minimum-cost-flow theorem is stated with the relevant hypotheses. Here the network is finite, capacities are nonnegative integers, the prescribed value \(B\) is integral, costs are rational, and feasibility has been established. Finite capacities also bound the objective, so negative arc costs cause no unboundedness issue. The integral optimum and polynomial-time computation claims are valid.
Convexity of absolute value gives nondecreasing incremental costs. Replacing a used later parallel arc with an unused earlier one preserves all flow balances and capacities and cannot increase cost. This justifies choosing an optimum with the required prefix property.
A flow of value \(B\) saturates every source and sink arc, since their respective total capacities equal \(B\). Hence the constructed matrix has precisely the required margins.
The telescoping identity is correct. Conversely, every feasible integer matrix supplies a feasible prefix flow. These two directions establish equality of the optimization problems up to the stated constant, and therefore global optimality.
The vertex and arc counts are correct. Each incremental cost has denominator dividing \(Q\), and its magnitude is at most one. Scaling by \(Q\) therefore yields integer costs of \(O(L)\) bits and preserves minimizers.
All network data have polynomial encoding length. The asserted polynomial-time flow computation consequently includes dependence on \(\log n\).
The recovery invariant is preserved at every iteration. The displayed inequality verifies Hall’s condition whenever \(N>0\), and the two vertex classes both have size \(m\). Hall’s theorem therefore applies.
The selected multiplicity is a positive integer. Subtracting it along a perfect matching preserves nonnegativity and decreases every row and column margin by the same amount.
Each iteration permanently removes at least one positive entry. Thus there are at most \(m^2\) iterations. The distinctness argument also holds: a recorded matching loses an edge permanently and cannot recur.
At termination, the residual matrix is zero. The recorded multiplicities sum to \(n\), and the rankings reproduce the optimal matrix exactly.
The stated output-length bound is valid when candidates are represented by their input indices. Matching computations and arithmetic on entries bounded by \(n\) take polynomial time.
The argument covers \(m=1\), \(n=1\), zero entries, integral entries, and arbitrary positive rational support masses. No step requires enumeration of all rankings or expansion into \(n\) voters.
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.