| paper | d4-conf-aaai-2015-0085 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even when every class of every type has size at most \(2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 6
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.
A unit interval of agents with distribution \(\mu\) over incomplete-preference types; each agent receives a complete ranking extending their type, and feasibility requires single crossing along the interval. The decision depends only on the positive-mass support \(T\), so it is exactly equivalent to the corresponding finite support-recognition problem.
The mirror covers the arbitrary-order hardness results for PO-SCC, WO-SCC, and IP-SCC; it leaves the fixed-order algorithms, the top-order results, and weakly single-crossing recognition aside.
The best mirror here is continuous recognition of single-crossing populations with incomplete preferences. Let \(C\) be the alternatives, and let \(T\) be the support of reported partial-order types, with positive rational masses \(\mu_t\) summing to \(1\). Each type is a complete description of what the instance knows about an agent’s preference: the partial order they reported. Mass \(\mu_t\) is the fraction of the population with that report.
Represent the population by \([0,1]\) with Lebesgue measure. A solution assigns each point \(x\) a type \(\theta(x)\), with \(\theta^{-1}(t)\) having measure \(\mu_t\), and a complete ranking \(\pi(x)\) extending that type’s partial order. The population is single-crossing if, for every pair \(a,b\), the agents preferring \(a\) to \(b\) form an initial or terminal interval of the axis. This is a feasibility question, so its objective is simply to decide whether such an assignment exists.
Although this definition allows a type’s mass to be split among positions and completions, splitting adds no power here. Along a single-crossing axis, each pair’s preference direction changes at most once; with finitely many alternatives, the complete rankings therefore occur in finitely many consecutive blocks. For each positive-mass type, we can choose a compatible ranking that occurs on a positive-measure part of the axis, then consolidate that type’s mass into a block with that ranking. Thus an exact finite witness is a permutation \(t_1,\ldots,t_\tau\) of the support and one complete extension \(\pi_i\) of each \(t_i\), such that the sequence \(\pi_1,\ldots,\pi_\tau\) changes direction at most once for each candidate pair. Give block \(i\) length \(\mu_{t_i}\). Conversely, any such witness defines a continuous population.
That equivalence makes the mirror especially plausible to the authors. Their paper explicitly says that in the arbitrary-voter-order problem duplicate votes can be removed without changing the answer. Stretching the resulting order of distinct reports into intervals preserves the same completion and single-crossing question. A plausible regime is a large consultation or survey in which many residents submit the same incomplete ranking of a fixed set of options: the population size \(n\) is much larger than the number \(\tau\) of distinct reports. The continuum is the population; the partial preferences and the unknown ordering remain the paper’s. This does not extend the outcome space or turn the question into an axiomatic one.
My lead is Cont-WO-SCC: given \(C\), a support \(T\) consisting only of weak-order types, and positive rational masses \(\mu_t\), decide whether there is an ordering of the types and a complete extension for each that yields a single-crossing continuous population. A weak order represents ranked tiers, including ties, so this is a natural large-survey model. The paper’s Corollary 6, proved there from the hardness construction, states that WO-SCC is NP-complete: deciding whether a profile consisting only of weak orders can be extended to total orders and permuted to become single-crossing is NP-complete. The continuous problem should also be NP-complete by the equivalence above.
Two further anchors show that this is not tied to weak orders alone. Cont-PO-SCC allows arbitrary partial-order types. The paper’s Theorem 5, proved there by reduction from BETWEENNESS, states that PO-SCC is NP-complete: given a profile of arbitrary partial orders, deciding whether some voter permutation and some total-order extensions make it single-crossing is NP-complete. Cont-IP-SCC restricts \(T\) to independent-pairs orders, where all incomparable pairs within each type are pairwise disjoint. The paper’s Theorem 7, also proved there, states that IP-SCC is NP-complete under that restriction. Both continuous problems ask the same precise existence question with their respective restrictions on \(T\).
I expect all three to be Class B: hardness transfers. Given a discrete instance, remove duplicate reports and assign equal positive mass to the remaining types. By the equivalence, the continuous instance is yes exactly when the discrete one is. Restoring duplicate voters as adjacent copies of the same completed ranking preserves single-crossing. The type order and completed rankings form a polynomial-size witness, so the continuous problems are in NP as well. Their complexity is therefore NP-complete, measured in the explicit input size \(m,\tau,L\). The hardness survives because the reduction’s constraints are about arranging preference types and alternatives, not about having indivisible individual voters.
The scope is the paper’s arbitrary-order extension-recognition problems, in the general, weak-order, and independent-pairs domains. It does not claim a mirror of every result in the paper, such as the fixed-order algorithms or weakly single-crossing recognition. A follow-up is to determine whether the open complexity of top-order recognition with arbitrary voter order changes under this population formulation, and which additional restrictions on partial-order types yield efficient algorithms.
The weak point is that mass values do no computational work in these recognition mirrors: only positive support matters. This is an exact high-multiplicity identity, not a case where fractional population mass makes the problem tractable or calls for continuous optimization. That limits what it contributes to the programme’s algorithmic story. But it is still a faithful mirror of a named NP-completeness result, and it marks a clear boundary: the discrete hardness survives because the hard part lies in the structure of the types and alternatives, not in voter multiplicity.
The strongest case against is that all three anchors—Theorem 5 for PO-SCC, Corollary 6 for WO-SCC, and Theorem 7 for IP-SCC—become the same support-only question when translated to a continuous population. Their restrictions differ, but each asks whether the reported types can be ordered and completed so that every pair of alternatives changes preference direction at most once.
Even the stronger version that lets a type’s mass split across positions and completions collapses to the discrete support problem. Given a feasible continuous population, choose one point of positive mass for each type and take its complete ranking. In their order along the axis, these representatives still satisfy single-crossing: restricting a sequence with at most one change for each candidate pair cannot create another change. Conversely, given one compatible completion per support type in a single-crossing order, place each type in a consecutive interval of length \(\mu_t\). So the continuous instance is feasible exactly when the profile containing one copy of each support type is feasible. The mass values and their bit lengths do no work.
That also answers the best version of the high-multiplicity story. A large consultation with many residents submitting the same incomplete rankings is plausible, but this paper’s exact recognition question is invariant to those repetitions; the paper itself notes that duplicate votes can be removed. The continuous formulation adds population proportions to an input whose feasibility depends only on which reports have positive mass. It supplies no mass-sensitive objective, constraint, or computational structure for continuous optimization. The three hardness results therefore do not yield three population mirrors; they yield one unchanged support-recognition problem, restated with interval lengths.
One could make the masses matter by asking for the largest mass that can be made single-crossing, or the least mass whose reports must be changed or discarded. Those may be worthwhile population problems, but they are weighted repair or approximation questions, not stronger formulations of the named exact-recognition results. They cannot rescue these anchors as mirrors of the paper.
This is a case against their *value as continuization results*, not a proof that the continuous question is ill-posed. The user’s standard explicitly allows a well-posed mirror with a dull answer, and the identity above may itself count as a useful dictionary. A realistic high-multiplicity survey scenario also exists. So the honest negative case is limited: the three anchors appear to add no population-dependent computation, but I cannot rule out a reader treating the exact equivalence as a worthwhile Class B mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.