Answer: \(\mathrm{NP}\)-complete; polynomial-time solvable in \(m,\tau,L\) if and only if \(\mathrm{P}=\mathrm{NP}\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe Partial Order Single-peaked Consistency problem is \textnormal{NP}-complete, even if the given preference profile contains a total order.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a fixed candidate set \(C\) and a finite-support rational distribution \(\mu\) over partial-order types \(P\) on \(C\), with at least one positive-mass type being a total order, decide whether there exists an axis \(A\) and, for every \(P\) with \(\mu_P>0\), a total-order completion \(L_P\supseteq P\) that is single-peaked with respect to \(A\).
An instance has a nonempty finite candidate set \(C\), with \(m=|C|\); this set is common to all types and its size is part of the input.
A society is given by its support: the list of the \(\tau\) distinct types with positive mass, each mass \(\mu_P\) a binary rational, with \(\sum_P\mu_P=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type \(P\) is a strict partial preference order on \(C\), encoded explicitly by its comparable pairs. Incomparability denotes missing information, and at least one support type is a total order.
An axis \(A\) is a total order on \(C\). A completion \(L_P\) is a strict total preference order preserving every comparison in \(P\); single-peakedness has its standard meaning for strict total preferences.
The decision problem asks whether there exist one common axis \(A\) and, for every support type \(P\), a completion \(L_P\) single-peaked with respect to \(A\).
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite lists of voters with strict partial preferences, this recognition problem is \(\mathrm{NP}\)-complete even when a total-order vote is present. With an axis supplied, recognition for partial preferences takes \(\mathcal{O}(m^4 n)\) time for \(n\) voters.
The problem is \(\mathrm{NP}\)-complete, using the finite-voter hardness theorem supplied in the question. Consequently, a polynomial-time algorithm in \(m,\tau,L\) exists only if \(\mathrm{P}=\mathrm{NP}\).
The essential observation is that feasibility depends on which preference types occur, not on their positive masses or multiplicities.
Consider a finite voter list \(P_1,\ldots,P_n\), and let \(Q_1,\ldots,Q_\tau\) be its distinct partial preference orders.
We claim that the voter list admits single-peaked completions on a common axis if and only if the distinct types do.
For the forward implication, take a witnessing common axis and completed voter orders. For each \(Q_j\), select one voter whose partial order equals \(Q_j\), and use that voter’s completion.
For the reverse implication, take a witnessing axis and a completion for each \(Q_j\). Give every voter with partial order \(Q_j\) that same completion. It preserves the voter’s comparisons and is single-peaked on the common axis.
This proves both implications. In particular, allowing repeated voters to choose different completions does not invalidate deduplication.
Use the supplied theorem: common-axis recognition for finite lists of strict partial preferences is \(\mathrm{NP}\)-hard even when a total-order vote is present.
Given such an instance, retain its candidate set and deduplicate its voter list, obtaining \(Q_1,\ldots,Q_\tau\). The support is nonempty, and a total-order type remains after deduplication.
We assign positive dyadic masses, so the construction works even if “binary rational” means a rational with a finite binary expansion. Set \(k=\lceil\log_2\tau\rceil\) and \(D=2^k\), and define
\(\mu_{Q_j}=1/D\) for \(1\leq j<\tau\), and \(\mu_{Q_\tau}=(D-\tau+1)/D\).
Because \(D\geq\tau\), every mass is positive. Their sum is
\(\sum_{j=1}^{\tau}\mu_{Q_j}=((\tau-1)+(D-\tau+1))/D=1\).
For \(\tau=1\), this construction simply assigns mass \(1\). Each mass requires \(\mathcal{O}(\log(\tau+1))\) bits.
Deduplication is polynomial-time: represent each relation by its comparison matrix and compare the matrices. The output contains at most as many types as the original voter list and adds only \(\mathcal{O}(\tau\log(\tau+1))\) bits for masses. Thus its total encoding length is polynomial in the source input length.
By Section 1, the source instance is feasible exactly when the constructed support instance is feasible. The masses impose no additional condition on the axis or completions. Every promise in the target problem is preserved, establishing \(\mathrm{NP}\)-hardness.
A certificate consists of one axis \(A\) and one completed total preference order \(L_P\) for each support type \(P\). After indexing candidates, its length is \(\mathcal{O}((\tau+1)m\log(m+1))\).
Verify that every proposed order is a permutation of the candidate set. For each type, verify that its completion preserves every explicitly given comparison.
Single-peakedness can also be checked directly. Write the proposed axis as \(a_1,\ldots,a_m\), and let \(r_P(c)\) be the position of candidate \(c\) in the proposed completion, with position \(1\) best. Let \(a_p\) be its top candidate. Check
\(r_P(a_j)>r_P(a_{j+1})\) for every \(j<p\), and \(r_P(a_j)<r_P(a_{j+1})\) for every \(p\leq j<m\).
These conditions say exactly that preferences strictly improve when approaching the peak from either side of the axis, which is the standard definition of single-peakedness for strict total preferences. They therefore provide a necessary and sufficient check.
Using indexed rank arrays, verification takes \(\mathcal{O}(L+\tau m^2)\) standard RAM operations. These operations involve candidate indices and ranks of \(\mathcal{O}(\log(m+1))\) bits, so verification is also polynomial in the binary input model. No mass arithmetic is needed on the promised inputs.
Hence the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.
When an axis is supplied, apply the recognition algorithm stated in the question to one voter per support type. Its running time is \(\mathcal{O}(L+\tau m^4)\), including input reading, under the theorem’s standard operation-count convention.
Enumerating all axes consequently gives a deterministic upper bound of \(\mathcal{O}(L+m!\,\tau m^4)\). Polynomial recognition for each fixed axis does not imply polynomial recognition when the axis must be found.
⟨structured verdict parsed — rendered above⟩
The prover’s argument correctly establishes \(\mathrm{NP}\)-completeness for the stated support representation. The reduction preserves all promises, deduplication preserves feasibility, and the certificate verifier is sound and polynomial. No major or minor issues were found.
The prover invokes exactly the hardness result supplied in USER_TASK: common-axis completion recognition for finite lists of strict partial preferences is \(\mathrm{NP}\)-hard even when a total-order vote is present.
Its hypotheses match the reduction’s source instances. The theorem is an explicit premise of the task, so the prover need not reproduce its proof. The supplied total-order vote also ensures that the source voter list is nonempty.
Assessment: Valid use of the supplied theorem.
Both implications are justified:
The argument correctly handles the possibility that repeated voters originally receive different completions: feasibility requires existence of suitable completions, so retaining any one witnessing completion for each repeated type suffices.
There are no constraints involving multiplicities or masses in the target’s feasibility definition.
Assessment: Correct equivalence, with no missing quantifier or compatibility condition.
For \(\tau\geq 1\), the prover defines \(k=\lceil\log_2\tau\rceil\) and \(D=2^k\). Thus \(D\geq\tau\), and the last numerator satisfies \(D-\tau+1\geq1\). All assigned masses are therefore positive.
The normalization calculation is correct:
\[ \frac{\tau-1}{D}+\frac{D-\tau+1}{D}=1. \]
The masses are dyadic, so they meet both the usual binary encoding of rationals and the narrower interpretation requiring finite binary expansions. Their stated encoding bound, \(\mathcal{O}(\log(\tau+1))\) bits per mass, is correct. The case \(\tau=1\) gives \(D=1\) and mass \(1\), as stated.
Deduplication retains the candidate set and the partial orders themselves. At least one total-order type remains, and the resulting support contains distinct types only.
Assessment: All target promises are preserved.
Representing explicitly given comparison relations by matrices and comparing those matrices is a polynomial-time deduplication procedure. Because source preferences contain their comparable pairs explicitly, equality of these relations is the relevant equality of types.
The output has at most as many types as the source has voters. The added mass data uses \(\mathcal{O}(\tau\log(\tau+1))\) bits, so the output length is polynomial in the source input length.
Section 1 establishes the required equivalence between source feasibility and target feasibility. The mass assignment introduces no further feasibility condition.
Assessment: A valid polynomial many-one reduction establishing \(\mathrm{NP}\)-hardness.
The certificate contains one axis and one completed preference order per support type. After indexing candidates, its stated size,
\[ \mathcal{O}((\tau+1)m\log(m+1)), \]
is polynomial in the explicit input parameters.
Checking that each proposed order is a permutation ensures that the axis and completions are strict total orders on exactly the given candidate set. Checking every input comparison ensures that each completion extends its corresponding partial preference order.
The single-peakedness inequalities have the correct directions. With rank \(1\) best:
The adjacent inequalities enforce precisely the required monotonicity on each side. Strict single-peakedness imposes no additional comparison requirement between candidates on opposite sides of the peak.
Boundary peaks are handled by empty index ranges. When \(m=1\), both sets of inequalities are empty, correctly accepting the unique preference order.
The bound \(\mathcal{O}(L+\tau m^2)\) is a valid, possibly loose, standard RAM operation bound. The prover explicitly distinguishes this operation count from binary-model complexity and correctly observes that the relevant indices and ranks have polynomial bit length. Omitting mass arithmetic is justified on the promised inputs.
Assessment: Sound and complete polynomial certificate verification; membership in \(\mathrm{NP}\) is established.
Applying the supplied-axis theorem to one voter per support type is justified by the deduplication equivalence. Its stated operation-count bound becomes \(\mathcal{O}(L+\tau m^4)\), including input reading.
There are \(m!\) total axes. Consequently, the deterministic exhaustive-search bound \(\mathcal{O}(L+m!\,\tau m^4)\) follows under the stated operation-count convention. Input reading can occur once before enumeration.
The prover correctly distinguishes polynomial recognition for a supplied axis from recognition when the axis must be found.
Assessment: Both runtime claims are justified.
The prover fully resolves the assigned decision problem. Its conclusion of \(\mathrm{NP}\)-completeness follows from the verified reduction and certificate verifier. The stated consequence concerning \(\mathrm{P}=\mathrm{NP}\) is correct.
No additional clarification or repair is required.
⟨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.