Answer: Polynomial-time solvable, including axis construction, in \(O(L+m\tau)\) word-RAM time; the decision problem belongs to \(\mathrm P\).
Proposition 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe single-peaked consistency problem can be solved in time O(nm).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\) alternatives and a finite-support distribution \(\mu\) over strict rankings, is there a linear order \(O\) such that every ranking \(t\) with \(\mu_t>0\) is single-peaked with respect to \(O\)? If so, output such an axis.
Let \(X\) contain \(m\geq 3\) alternatives. Types are strict rankings of all alternatives in \(X\); single-peakedness has its standard meaning with respect to a linear axis on \(X\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Determine whether there is a linear order \(O\) on \(X\) such that every supported ranking is single-peaked with respect to \(O\), and output such an axis when one exists.
Is this problem solvable in polynomial time in \(m,\tau,L\), including constructing a compatible axis, or is its decision version \(\mathrm{NP}\)-hard?
For a discrete profile of \(v\) voters and \(m\) alternatives, consistency can be decided and a compatible axis constructed in \(O(mv)\) time: Escoffier, Lang, and Öztürk, [Single-peaked consistency and its complexity](https://doi.org/10.3233/978-1-58603-891-5-366).
The problem is polynomial-time solvable, including construction of a compatible axis. The recognition algorithm takes \(O(m\tau)\) time after extracting the rankings; allowing for reading the entire binary input gives \(O(L+m\tau)\) time under the usual word-RAM convention.
Write the supported strict rankings as \(r_1,\ldots,r_\tau\), with masses \(\mu_1,\ldots,\mu_\tau>0\). For a ranking \(r\), let \(\mathcal A(r)\) denote the set of linear axes with respect to which \(r\) is single-peaked.
The society’s set of compatible axes is exactly
\[
\mathcal A_{\mathrm{society}}=\bigcap_{t=1}^{\tau}\mathcal A(r_t).
\]
Indeed, an axis belongs to this intersection if and only if every supported ranking is single-peaked on it, which is precisely the requirement in the question.
Construct a discrete profile \(P=(r_1,\ldots,r_\tau)\) containing one voter for each supported type. Its compatible axes satisfy
\[
\mathcal A(P)=\bigcap_{t=1}^{\tau}\mathcal A(r_t)=\mathcal A_{\mathrm{society}}.
\]
Thus the reduction preserves all compatible axes, as well as the decision answer. The numerical masses do not enter this equality.
Use the stated theorem of Escoffier, Lang, and Öztürk: for an explicitly listed profile of \(v\) strict rankings of \(m\) alternatives, an algorithm decides single-peaked consistency and constructs a compatible axis when one exists in \(O(mv)\) time. Both correctness and construction are established in their [paper, Section 3, Propositions 1–2](https://www.lamsade.dauphine.fr/~lang/papers/elo-ecai08.pdf).
Apply it as follows:
The theorem’s hypotheses hold: \(P\) is explicitly listed, every ranking is strict and complete, and every voter ranks the same set \(X\).
If the algorithm outputs an axis, the equality \(\mathcal A(P)=\mathcal A_{\mathrm{society}}\) proves that it satisfies the original requirement. If it rejects, that equality proves that no axis satisfies the original requirement. This establishes correctness in both directions.
Reading the input costs \(O(L)\), and recognition and construction cost \(O(m\tau)\). Consequently, the total word-RAM running time is \(O(L+m\tau)\).
This also yields polynomial bit complexity: the recognition algorithm uses indices, counters, and rank positions of polynomially bounded size, so its word operations admit polynomial-cost bit simulation. The masses are promised valid and can be skipped; no rational arithmetic or expansion into voters is needed.
In particular, clearing denominators and replicating rankings according to their masses would be unnecessary and could produce exponentially many voters.
The decision problem therefore belongs to \(\mathrm P\). It could be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions only if \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output fully resolves the task. The reduction is exact, the cited theorem applies, and both decision and axis construction run in polynomial time. No major or minor issues were found.
The definition of \(\mathcal A(r)\) is unambiguous: it contains exactly the linear axes compatible with ranking \(r\). The equality
\[
\mathcal A_{\mathrm{society}}=\bigcap_{t=1}^{\tau}\mathcal A(r_t)
\]
follows directly from the task’s requirement that every supported ranking be single-peaked on the same axis. There is no additional condition involving the masses.
All listed masses are positive by hypothesis, so every listed ranking must be included. Ignoring their numerical values is therefore justified.
The discrete profile \(P=(r_1,\ldots,r_\tau)\) contains exactly one voter for each supported ranking. By the definition of profile single-peakedness, its compatible axes are precisely the same intersection. Consequently, the reduction preserves both existence and every valid output axis.
The substitution \(v=\tau\) is correct. It does not substitute the number of possible rankings or expand rational masses into voter multiplicities.
The prover states the required theorem with its input assumptions, decision guarantee, construction guarantee, and running time. The cited source confirms that Section 3, Proposition 1 provides a compatible axis whenever one exists and detects inconsistency otherwise; Proposition 2 establishes the linear product running time. The paper uses different variable names for voters and alternatives, but the product bound translates correctly to \(O(mv)\). [Escoffier, Lang, and Öztürk, Section 3](https://www.lamsade.dauphine.fr/~lang/papers/elo-ecai08.pdf).
The hypotheses are satisfied: the rankings are explicitly listed, strict, complete, and defined on the same alternative set. The task assumes \(m\geq3\), consistent with the paper’s setting. Also, \(\tau\geq1\) follows from positive masses summing to one, so an empty-profile edge case does not arise.
Because this theorem is stated and its hypotheses are verified, the prover need not reproduce its internal algorithm or proof.
If the discrete algorithm returns an axis, equality of the compatible-axis sets proves that it satisfies every supported ranking.
If the algorithm rejects, its theorem guarantees that the discrete profile has no compatible axis. The same equality then excludes a compatible axis for the society. Neither implication depends on an unstated property of the masses.
Reading the input costs \(O(L)\). Extracting the explicitly listed rankings and applying the theorem costs \(O(m\tau)\) under the stated word-RAM convention. Thus \(O(L+m\tau)\) is a valid upper bound, including construction and output.
The polynomial bit-complexity conclusion is also justified: indices, rank positions, and counters have polynomially bounded numerical values and therefore polynomially bounded bit lengths. Simulating the word operations consequently preserves polynomial time.
The input is promised to contain valid positive rational masses summing to one. The algorithm therefore need not verify this promise or perform rational arithmetic. The observation that denominator clearing could require exponentially many voters is correct and is not used as a premise of the proof.
The established algorithm places the decision problem in \(\mathrm P\) and constructs a compatible axis in polynomial time. The final qualification concerning \(\mathrm{NP}\)-hardness under polynomial-time many-one reductions correctly avoids claiming an unconditional separation between \(\mathrm P\) and \(\mathrm{NP}\).
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.