Answer: Polynomial-time solvable in \(m,\tau,L\).
Theorem 1 (Linear time and space) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateUnder Assumption~\ref{asm:bounded}, Algorithm~\ref{alg:pgD} runs in $\mathcal{O}(m)$ time and uses $\mathcal{O}(m)$ space.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(V\) and an explicit support of \(\tau\) complete evaluator judgment patterns with rational masses \(\mu_t\), compute the paper’s greedy denoising output: its total order, backward-edge set, and retained DAG, using edge weights \(W_\mu(u,v)=\sum_t\mu_t\mathbf{1}[t\text{ prefers }u\text{ to }v]\).
Let \(V=\{v_1,\ldots,v_m\}\), with \(m\geq1\), have the fixed label order \(v_1<\cdots<v_m\). A type specifies, for every unordered pair, either a strict preference in one direction or a tie; its judgments need not be transitive, and ties contribute no arcs.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
Define \(W_\mu(u,v)=\sum_t\mu_t\mathbf{1}[t\text{ strictly prefers }u\text{ to }v]\) for distinct candidates and \(A_0=\{(u,v):W_\mu(u,v)>0\}\). Initialize a working graph \(H=(V,A_0,W_\mu)\) and empty lists \(s_1,s_2\).
Repeat the following round until \(H\) is empty: repeatedly remove a sink, prepending it to \(s_2\); then repeatedly remove a source, appending it to \(s_1\); if vertices remain, remove a vertex maximizing \(\delta_H(u)=\sum_{(u,v)\in A(H)}W_\mu(u,v)-\sum_{(v,u)\in A(H)}W_\mu(v,u)\), appending it to \(s_1\). Each removal deletes all incident arcs; all ties between eligible vertices use the smallest label. An isolated vertex qualifies as a sink.
The required output is \(s=s_1\Vert s_2\), \(R(s)=\{(u,v)\in A_0:\operatorname{pos}_s(u)>\operatorname{pos}_s(v)\}\), and the retained weighted DAG \((V,A_0\setminus R(s),W_\mu)\).
Is computing this output solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For discrete ensembles with a fixed number \(k\) of evaluators and integral arc weights in \(\{0,\ldots,k\}\), greedy denoising has a stated linear time and space bound in the number of positive arcs, using connectedness to absorb the vertex count.
For arbitrary real arc weights, a stated bound is \(O(a\log m)\) time and \(O(a)\) space on connected graphs, where \(a=|A_0|\); this is a graph-operation bound rather than a bit-complexity bound for rational support input.
Computing the specified output is polynomial-time solvable in \(m,\tau,L\). The crucial point is that all score comparisons can be performed exactly using integers of polynomial bit length.
Here, rational input uses the usual binary encoding of numerators and denominators; this includes dyadic rational masses.
Write each positive mass as \(\mu_t=p_t/q_t\), where \(p_t,q_t\) are positive integers. Define
\(D=\prod_{t=1}^{\tau}q_t,\qquad n_t=p_t(D/q_t).\)
Each division is exact, and the normalization hypothesis gives
\(\sum_{t=1}^{\tau}n_t=D.\)
For distinct candidates, define the integer weight
\(C(u,v)=\sum_{t=1}^{\tau}n_t\mathbf{1}[t\text{ strictly prefers }u\text{ to }v].\)
Consequently,
\(W_\mu(u,v)=C(u,v)/D,\qquad 0\leq C(u,v)\leq D.\)
In particular, \((u,v)\in A_0\) exactly when \(C(u,v)>0\).
Although the numerical value of \(D\) can be large, its binary length is small:
\(\log_2 D=\sum_{t=1}^{\tau}\log_2 q_t\leq L.\)
Thus \(D\), every \(n_t\), and every \(C(u,v)\) have \(O(L)\) bits. Constructing \(D\), the \(n_t\), and the matrix \(C\) requires only polynomially many exact integer operations.
Let \(S\subseteq V\) be the set of remaining vertices. Since removals only delete incident arcs, the working graph is always the subgraph induced by \(S\). Define its integer score by
\(\Delta_S(u)=\sum_{v\in S\setminus\{u\}}C(u,v)-\sum_{v\in S\setminus\{u\}}C(v,u).\)
The prescribed score satisfies
\(\delta_H(u)=\Delta_S(u)/D.\)
Because \(D>0\), maximizing \(\delta_H\) is exactly equivalent to maximizing \(\Delta_S\), including equality of scores. Also,
\(\lvert\Delta_S(u)\rvert\leq (|S|-1)D.\)
Hence every score has \(O(L+\log(m+1))\) bits.
Maintain, for each active vertex, its incoming and outgoing positive-arc counts and its integer score. These determine sinks and sources exactly: a sink has outgoing count zero, and a source has incoming count zero.
When removing \(u\), update each remaining vertex \(v\) as follows:
The score update follows directly by deleting the outgoing contribution \(C(v,u)\) and the incoming contribution \(-C(u,v)\).
Execute the phases in precisely the stated order: exhaust sinks, then exhaust sources, then perform one maximum-score removal if vertices remain. For each selection, scan active vertices in increasing label order. Choose the first eligible sink or source; for score maximization, replace the current choice only upon finding a strictly larger score. This implements every required label tie-break.
Initially, the maintained counts and scores are correct by construction. The update formulas preserve their correctness after each removal. Induction on the number of removals therefore proves that this simulation makes exactly the prescribed choices.
Set \(B=L+\lceil\log_2(m+1)\rceil+3\), which bounds the lengths of the integers used, including intermediate score updates.
Using ordinary quadratic-time integer multiplication and division:
For the simulation, each nonempty round removes at least one vertex: if the sink and source phases leave vertices, the maximum-score phase removes one. There are therefore at most \(m\) rounds and exactly \(m\) removals.
Each successful selection removes a vertex. Each round additionally has at most two unsuccessful scans, one ending each of the sink and source phases. Thus there are \(O(m)\) selection scans, each inspecting at most \(m\) vertices. Each removal also updates at most \(m-1\) remaining vertices. All score comparisons and updates cost \(O(B)\) bit operations.
The simulation consequently costs \(O(m^2B)\) bit operations. An overall bound is
\(O\bigl(\tau B^2+(\tau m^2+m^2)B\bigr),\)
which is polynomial in \(m,\tau,L\). Storage is likewise polynomial.
This argument includes isolated vertices and disconnected graphs; no connectedness assumption is needed.
Record source and maximum-score removals in their removal order to form \(s_1\). Record sink removals separately and reverse that record to form \(s_2\), exactly implementing repeated prepending. Since every vertex is removed once, \(s=s_1\Vert s_2\) is a permutation of \(V\).
Compute each vertex’s position in \(s\), then inspect every positive arc. Put \((u,v)\) in \(R(s)\) exactly when \(\operatorname{pos}_s(u)>\operatorname{pos}_s(v)\); otherwise retain it with weight \(C(u,v)/D\). This requires another \(O(m^2B)\) bit operations, including writing the rational weights.
Every retained arc strictly increases position in \(s\). A directed cycle would therefore force a strict increase in position all the way back to its starting vertex, which is impossible. The retained graph is a DAG.
Thus the complete prescribed output—not merely its ordering—is computable in polynomial time. The cited graph-operation bounds are compatible with this result; exact rational arithmetic supplies the additional bit-complexity justification.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned task correctly: the complete prescribed output is computable in polynomial time in \(m,\tau,L\). The argument provides an exact simulation, controls the bit lengths of all arithmetic, and constructs all three required outputs. No major or minor mathematical issues were found.
The prover explicitly interprets binary rational input using binary-encoded numerators and denominators. This covers the intended rational support representation, including dyadic masses.
Since every mass is positive and the masses sum to one, \(0<p_t\leq q_t\). Consequently, the defined integers satisfy \(0<n_t\leq D\). Every division \(D/q_t\) is exact because \(q_t\) is a factor of \(D\).
Multiplying the normalization identity by \(D\) correctly gives
\[
\sum_{t=1}^{\tau}n_t=D.
\]
Thus each \(C(u,v)\), being a sum over a subset of these nonnegative integers, lies between zero and \(D\). The identities relating \(C\) to \(W_\mu\), including the characterization of positive arcs, are exact.
The denominator-length estimate is valid: the sum of the logarithms of the denominators is bounded by the number of bits used to encode them, hence by \(L\). The distinction between \(\log_2D\) and binary length introduces only an additive constant. All claimed \(O(L)\) bit-length bounds follow.
Finding: Correct.
Deleting vertices and all their incident arcs leaves precisely the induced graph on the active set \(S\). Summing over all other active vertices is legitimate because absent arcs have integer weight zero.
The relation
\[
\delta_H(u)=\Delta_S(u)/D
\]
holds throughout the simulation. Since \(D\) is fixed and positive, integer comparisons preserve both score order and score equality.
Each of the outgoing and incoming sums lies between zero and \((|S|-1)D\). Their difference therefore has absolute value at most \((|S|-1)D\), as claimed.
Both arc-count updates are correct, including when both directed arcs between \(u\) and \(v\) exist. The score update removes the outgoing contribution \(C(v,u)\) and the incoming contribution \(-C(u,v)\), yielding exactly the stated formula.
Finding: Correct.
Outgoing count zero identifies a sink, and incoming count zero identifies a source. Isolated vertices satisfy both conditions and are processed in the sink phase, as required.
Scanning labels in increasing order and selecting the first eligible vertex implements the sink and source tie-breaks. For maximum-score selection, changing the selected vertex only upon a strict improvement retains the smallest label among maximizers.
The specified phase order is preserved. In particular, a sink created during the source phase need not trigger an immediate return to the sink phase; the prover follows the round structure in the task.
Initialization and the update formulas justify the stated induction that every removal matches the prescribed procedure.
Finding: Correct.
The chosen \(B\) bounds weights, scores, counts, and intermediate score-update values. The additional constant accommodates signs and the temporary subtraction or addition of one weight.
The preprocessing bounds correctly account for denominator products, exact divisions, numerator multiplications, and accumulation of the weight matrix using ordinary integer arithmetic.
Every nonempty round removes at least one vertex. Hence there are at most \(m\) rounds and exactly \(m\) removals. Successful selection scans number \(m\), and each round contributes at most two unsuccessful phase-ending scans. Therefore the total number of scans is \(O(m)\).
Each scan inspects at most \(m\) vertices; each removal updates at most \(m-1\) vertices. The resulting \(O(m^2B)\) simulation bound and the displayed overall polynomial bound follow.
Finding: Correct. The argument requires no unverified external theorem application.
Reversing the sink-removal record implements repeated prepending exactly. The other removals are recorded in their required append order. Every vertex appears once, so concatenation produces the required permutation.
The subsequent position comparisons implement the definition of \(R(s)\) exactly. Writing retained weights as \(C(u,v)/D\) preserves their values and uses polynomial output length; reduced fractions are not required by the task.
Every retained arc increases position strictly. The given cycle contradiction therefore establishes acyclicity.
Finding: Correct; all required outputs are addressed.
For \(m=1\), the sole vertex is an isolated sink and the algorithm produces the required singleton ordering and empty arc sets. The same reasoning handles an entirely edgeless graph and disconnected graphs.
The proof does not rely on connectedness, bounded integral weights, or the quoted graph-operation bounds. Its explicit rational bit-complexity analysis independently settles the support-input problem.
Finding: Correct.
No additional clarification, missing lemma, or mathematical 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.