Answer: \(\mathrm{NP}\)-complete, even when every class of every type has size at most \(2\).
Corollary 6 — class: hardness
Given a candidate set \(C\), a finite support \(T\) of partial-order types, and positive rational masses \(\mu_t\) summing to \(1\), decide whether there are measurable assignments \(t(x)\in T\) and complete rankings \(\pi(x)\) for \(x\in[0,1]\), with \(\lambda(\{x:t(x)=t\})=\mu_t\) and \(\pi(x)\) extending \(t(x)\) almost everywhere, such that for every pair \(a,b\in C\), the agents ranking \(a\) above \(b\) form an initial or terminal interval of the axis. Restrict \(T\) to weak orders for Corollary 6.
Let \(C\) be a nonempty candidate set, with \(m=|C|\). Each type is a weak order, encoded as an ordered partition of \(C\) into nonempty classes: earlier classes strictly outrank later ones; comparisons within a class are unspecified and may be resolved arbitrarily in a strict total-order extension.
A society is given by its support: the list \(T\) of the \(\tau\) distinct types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
Call the instance feasible if there exist measurable maps \(t:[0,1]\to T\) and \(\pi:[0,1]\to\mathcal L(C)\), where \(\mathcal L(C)\) denotes strict total orders, such that \(\lambda(t^{-1}(\{s\}))=\mu_s\) for every \(s\in T\), and \(\pi(x)\) extends \(t(x)\) almost everywhere; \(\lambda\) is Lebesgue measure.
For every distinct \(a,b\in C\), the set \(\{x:a\succ_{\pi(x)}b\}\) must agree up to a null set with an initial or terminal interval of \([0,1]\), allowing empty and full intervals. Type locations are freely chosen, and a type's mass may be split among locations and extensions.
Is deciding feasibility solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite lists of weak orders, deciding whether strict total-order extensions admit some single-crossing voter ordering is \(\mathrm{NP}\)-complete ([original result](https://ojs.aaai.org/index.php/AAAI/article/view/9321)); the [full version](https://martin.lackner.xyz/publications/incompletesc-full.pdf) establishes hardness even when every class has size at most \(2\).
No result settling this exact continuous feasibility problem was identified in the literature search.
The problem is \(\mathrm{NP}\)-complete, even when every class of every type has size at most \(2\).
The central fact is that continuous feasibility is equivalent to finite single-crossing completion of the support. In particular, feasibility depends only on which types have positive mass, not on their masses.
Call an ordered list of strict total orders single-crossing if, for every distinct pair \(a,b\), the binary sequence recording whether \(a\) ranks above \(b\) changes value at most once.
Proposition. For any prescribed positive masses \((\mu_s)_{s\in T}\) summing to \(1\), continuous feasibility is equivalent to the existence of:
such that \(r_1,\ldots,r_\tau\) is single-crossing.
Suppose measurable maps \(t,\pi\) witness feasibility. For every ordered pair of distinct candidates, put
\(A_{ab}=\{x\in[0,1]:a\succ_{\pi(x)}b\}\).
By hypothesis, there is an initial or terminal interval \(I_{ab}\) such that
\(\lambda(A_{ab}\mathbin{\triangle}I_{ab})=0\).
Let \(N_0\) be the null set where \(\pi(x)\) fails to extend \(t(x)\), and define
\(N=N_0\cup\bigcup_{a\ne b}(A_{ab}\mathbin{\triangle}I_{ab})\).
There are finitely many candidate pairs, so \(N\) is null. Consequently, for every \(s\in T\),
\(\lambda(t^{-1}(\{s\})\setminus N)=\mu_s>0\).
Choose one point \(x_s\) from this set for each type. These points are distinct because their type fibers are disjoint. Enumerate them increasingly:
\(x_{s_1}<x_{s_2}<\cdots<x_{s_\tau}\),
and set \(r_i=\pi(x_{s_i})\). Each \(r_i\) extends \(s_i\).
For any pair \(a,b\), all selected points lie outside \(N\), hence
\(a\succ_{r_i}b\quad\Longleftrightarrow\quad x_{s_i}\in I_{ab}\).
The points belonging to an initial interval form a prefix of this increasing list; those belonging to a terminal interval form a suffix. Thus every pairwise comparison changes at most once. This proves finite single-crossing completion.
Conversely, suppose \(s_1,\ldots,s_\tau\) and \(r_1,\ldots,r_\tau\) satisfy the proposition. Define cumulative masses
\(p_0=0,\qquad p_i=\sum_{j=1}^{i}\mu_{s_j}\).
Partition the unit interval into consecutive blocks \(B_i=[p_{i-1},p_i)\), with the last block including \(1\). Define \(t(x)=s_i\) and \(\pi(x)=r_i\) on \(B_i\).
These maps are measurable, each type has its prescribed mass, and every assigned total order extends its type.
For every pair \(a,b\), single-crossing means that the indices satisfying \(a\succ_{r_i}b\) form a prefix or suffix, possibly empty or full. The union of their consecutive blocks is therefore an initial or terminal interval, up to endpoint conventions. This is exactly the required continuous condition.
This completes the proof of the proposition.
Consequence. Every feasible instance has a witness in which each type occupies one consecutive block and uses one strict extension.
The cited finite hardness problem takes a list of weak orders, whereas the continuous input lists distinct support types. The following observation bridges that distinction.
Lemma. A finite list admits single-crossing strict extensions in some voter ordering if and only if its list of distinct types does.
Proof. Given a completion of the original list, retain one occurrence of each type. Restricting a prefix or suffix to an ordered subsequence again gives a prefix or suffix, so the retained extensions remain single-crossing.
Conversely, given a completion of the distinct types, replace each type’s chosen extension by as many consecutive identical copies as its multiplicity in the original list. Repeating a binary comparison value consecutively cannot introduce another change. Each copy extends the corresponding original type. Thus this produces a completion of the entire list. \(\square\)
Elkind, Faliszewski, Lackner, and Obraztsova establish that deciding finite single-crossing completion in an unspecified voter ordering is \(\mathrm{NP}\)-complete for weak orders, even when every antichain has size at most \(2\). Their weak orders are precisely ordered partitions with unspecified comparisons inside classes, so the restriction means that every class has size at most \(2\). See [Theorem 7 of the full version](https://martin.lackner.xyz/publications/incompletesc-full.pdf).
Take a nonempty instance of that finite problem. Remove duplicate types, obtaining \(T=\{s_1,\ldots,s_\tau\}\), and retain the same candidate set.
Assign the following positive dyadic rational masses:
\(\mu_{s_i}=2^{-i}\quad\text{for }1\le i<\tau,\qquad \mu_{s_\tau}=2^{-(\tau-1)}.\)
For \(\tau=1\), this assigns mass \(1\). In general,
\(\sum_{i=1}^{\tau}\mu_{s_i}=\bigl(1-2^{-(\tau-1)}\bigr)+2^{-(\tau-1)}=1.\)
Each mass has a binary rational encoding of length \(O(\tau)\), even when its denominator is written explicitly in binary. The total mass encoding therefore has length \(O(\tau^2)\). Duplicate removal and construction of the output are polynomial-time operations.
By the duplicate-removal lemma and the proposition,
\(\text{original finite instance is completable}\quad\Longleftrightarrow\quad\text{constructed continuous instance is feasible}.\)
The reduction does not change any type’s classes. Hence continuous feasibility is \(\mathrm{NP}\)-hard even with class sizes at most \(2\).
A certificate consists of an ordering of the \(\tau\) support types and one strict total-order extension for each type.
The verifier checks that:
Using candidate positions and class indices, the extension and single-crossing checks take \(O(\tau m^2)\) operations. The certificate has polynomial length, and no continuous maps need to be encoded: the proposition proves that this finite certificate is both necessary and sufficient.
Therefore the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. The equivalence, duplicate-removal argument, reduction, and membership proof are rigorous. I found no major or minor issues.
The definition used by the prover is appropriate: for each distinct candidate pair, the comparison sequence changes value at most once. For a binary sequence, this is equivalent to the indices carrying either comparison forming a prefix or suffix, allowing empty and full sets.
This matches the continuous requirement after restricting an initial or terminal interval to increasingly ordered sample points.
Every step of this direction is justified.
\[
\lambda\bigl(t^{-1}(\{s\})\setminus N\bigr)=\mu_s>0.
\]
Thus every required selection exists. Distinct types have disjoint fibers, so the selected points are distinct and can be ordered strictly increasingly.
The argument does not assume that type fibers are intervals or that a type uses only one extension in the original witness. Selecting one point from each positive-measure fiber is sufficient for the conclusion claimed.
The construction meets every requirement of the task.
The asserted consequence—that a feasible instance has a witness using one block and one extension per type—follows from the two directions already proved. Mass independence is also established for all prescribed positive masses summing to \(1\).
Both directions are correct.
For the forward direction, retaining one occurrence per type produces an ordered subsequence of the completed profile. Restricting a binary sequence with at most one change to a subsequence cannot create additional changes. The retained order still extends the retained type.
For the reverse direction, consecutive repetition of each chosen extension preserves every pairwise comparison sequence’s number of changes. Every repeated extension remains valid for its corresponding original occurrence.
The lemma therefore addresses the distinction between a finite list with multiplicities and a support containing distinct types.
The citation is accurate. Theorem 7 of the linked full version states that WO-SCC is NP-complete even for votes with antichains of size at most \(2\). Its definitions specify strict extensions of weak orders and permit choosing the voter ordering. Its weak orders are ordered classes with comparisons unspecified within each class, exactly as required here. [Full version, definitions and Theorem 7](https://martin.lackner.xyz/publications/incompletesc-full.pdf).
In an ordered-partition weak order, an antichain is contained within one class, and every class is an antichain. Thus the theorem’s restriction is precisely the prover’s class-size restriction.
The theorem supplies the required finite source problem; it is not being applied to a fixed voter ordering or to a different interpretation of ties. Restricting to nonempty source instances does not remove the stated hardness.
The mass calculation is correct.
For \(\tau=1\), the sole mass is \(1\). For \(\tau\geq2\),
\[
\sum_{i=1}^{\tau-1}2^{-i}=1-2^{-(\tau-1)},
\]
and adding the last mass yields total mass \(1\). All masses are positive dyadic rationals.
An explicitly encoded denominator \(2^i\) has binary length \(i+1\), so the claimed \(O(\tau)\) bound per mass and \(O(\tau^2)\) total bound are valid. The fact that the final two masses coincide when \(\tau\geq2\) causes no problem: masses need not be distinct.
Duplicate removal is polynomial for explicitly encoded ordered partitions. The resulting support size is bounded by the original list length, so the mass construction has polynomial output length.
The reduction’s equivalence follows directly from the duplicate-removal lemma and the continuous–finite equivalence. It preserves every type’s classes, so it also preserves the restriction that classes have size at most \(2\).
The certificate specifies all necessary finite choices: a permutation of the support and one candidate permutation for each type.
The stated checks verify that every extension is a strict total order respecting all comparisons between classes, and that every comparison sequence changes at most once. Candidate positions and class indices support the claimed \(O(\tau m^2)\) operation bound. Their encodings have polynomial bit length, so this is a polynomial-time verification procedure.
The equivalence proposition proves necessity and sufficiency of this certificate; no encoding of arbitrary measurable maps is required.
The allowed edge cases are covered:
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.