Answer: \(\mathrm{NP}\text{-hard}\)
Proposition 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven two SR instances I and I′ and an integer ℓ, deciding whether dswap(I, I′) ≤ℓis NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two societies with finite type sets \(T,T'\), rational masses \(\mu,\nu\), and weak rankings of types that tie members of each type, decide whether there is a coupling \(\pi\) with marginals \(\mu,\nu\) such that the probability of reversed strict comparisons is at most \(q\). Compute that probability by drawing three matched type pairs independently from \(\pi\), and charging one when the source focal type ranks the source alternatives one way while the aligned focal type ranks the aligned alternatives in the opposite order; tied comparisons contribute zero.
Each society is an atomless population given by its support: a nonempty list of types with positive binary rational masses summing to \(1\). Write \(\tau=|T|\), \(\tau'=|T'|\); these are support sizes, not numbers of possible types.
Each type \(a\in T\) has a complete weak order \(\succeq_a\) over \(T\), including its own type; all individuals of a type share preferences, and alternatives of the same type are tied. Define the second society analogously. Individual self-comparisons have probability zero; repeated type labels remain allowed.
The input also contains a binary rational threshold \(q\in[0,1]\). A coupling is a real matrix \(\pi\geq0\) satisfying \(\sum_{a'\in T'}\pi_{aa'}=\mu_a\) and \(\sum_{a\in T}\pi_{aa'}=\nu_{a'}\).
Draw \((A,A'),(B,B'),(C,C')\) independently from \(\pi\). Set \(D(\pi)=\Pr[(B\succ_A C\land C'\succ'_{A'}B')\lor(C\succ_A B\land B'\succ'_{A'}C')]\). A tie in either comparison contributes zero; do not condition on distinct type labels.
The decision problem asks whether some coupling satisfies \(D(\pi)\leq q\). Let \(L\) be the total input bit length and \(m=\max\{\tau,\tau'\}\), the maximum number of ranked alternatives; state running times in \(m,\tau,\tau',L\).
Is this continuous reversed-comparison coupling decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For two finite Stable Roommates instances with the same even number of agents, complete strict preferences over other agents, and integer threshold \(\ell\), deciding whether the minimum, over agent bijections, of the summed Kendall swap distances between aligned preference orders is at most \(\ell\) is \(\mathrm{NP}\)-complete. [Source](https://doi.org/10.1613/jair.1.15213).
No result settling exactly the continuous decision problem above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-hard, even under all of the following restrictions:
This restricted problem is also \(\mathrm{NP}\)-complete. The proof handles real couplings directly.
Consider societies in which every type ranks itself first and ties all other types. Thus, for source types,
\[ b\succ_a c\quad\Longleftrightarrow\quad b=a\text{ and }c\ne a, \]
and the analogous equivalence holds in the target society.
Fix a coupling \(\pi\), and condition on \((A,A')=(a,a')\). The first reversal event requires
\[ B=a,\qquad B'\ne a',\qquad C\ne a,\qquad C'=a'. \]
Because the second and third draws are independent, its conditional probability is
\[ \left(\sum_{b'\ne a'}\pi_{ab'}\right) \left(\sum_{c\ne a}\pi_{ca'}\right) =(\mu_a-\pi_{aa'})(\nu_{a'}-\pi_{aa'}). \]
The other reversal event has the same conditional probability, by exchanging the second and third draws. The two events are disjoint. Multiplying by the probability \(\pi_{aa'}\) of the conditioning event and summing gives
\[ D(\pi)=2\sum_{a\in T}\sum_{a'\in T'} \pi_{aa'}(\mu_a-\pi_{aa'})(\nu_{a'}-\pi_{aa'}). \tag{1} \]
Every summand is nonnegative: the marginal constraints imply \(\pi_{aa'}\leq\mu_a\) and \(\pi_{aa'}\leq\nu_{a'}\).
Repeated type labels are essential here. For example, \(A=B=a\) occurs with positive probability, although the sampled individuals are distinct almost surely. Formula (1) uses exactly the sampling convention in the question.
Suppose additionally that
\[ \mu_a<\nu_{a'}\qquad\text{for every }a\in T,\ a'\in T'. \tag{2} \]
For every coupling entry, \(\nu_{a'}-\pi_{aa'}\geq\nu_{a'}-\mu_a>0\). Consequently, formula (1) implies
\[ D(\pi)=0 \quad\Longleftrightarrow\quad \pi_{aa'}\in\{0,\mu_a\}\text{ for every }a,a'. \tag{3} \]
Indeed, a finite sum of nonnegative terms is zero precisely when each term is zero; under (2), the corresponding term vanishes precisely when \(\pi_{aa'}=0\) or \(\pi_{aa'}=\mu_a\).
Because each row has positive sum \(\mu_a\), condition (3) says that exactly one entry in each row equals \(\mu_a\). Thus a zero-reversal coupling assigns every source type wholly to one target type.
Conversely, any such assignment satisfying the target marginal constraints gives a coupling with \(D(\pi)=0\).
In particular, when there are two target types of mass \(\frac12\) and every source mass is smaller than \(\frac12\),
\[ \exists\pi:\ D(\pi)=0 \quad\Longleftrightarrow\quad \exists I\subseteq T:\ \sum_{a\in I}\mu_a=\frac12. \tag{4} \]
This equivalence applies to arbitrary real couplings.
We use the classical \(\mathrm{NP}\)-complete problem PARTITION: given positive binary integers \(w_1,\ldots,w_n\), determine whether some subset sums to half their total. See [the PARTITION discussion in *Computational Intractability*](https://hardness.mit.edu/drafts/2025-01-05.pdf).
Let \(W=\sum_{i=1}^n w_i\), and let \(H\) be the smallest power of two strictly greater than \(2W\). Hence
\[ 2W<H\leq4W. \]
Construct \(n+2\) source types with masses
\[ \mu_i=\frac{w_i}{H}\quad(1\leq i\leq n), \qquad \mu_{n+1}=\mu_{n+2}=\frac{H-W}{2H}. \]
These masses are positive dyadic rationals, and their sum is
\[ \frac WH+2\frac{H-W}{2H}=1. \]
Every source mass is strictly smaller than \(\frac12\). For the original types this follows from \(w_i\leq W<H/2\); for the two additional types it follows from \(0<W<H\).
Construct two target types \(x,y\), each of mass \(\frac12\). In both societies, every type ranks itself first and ties all remaining types. Set \(q=0\).
By (4), the constructed instance is a yes-instance precisely when some subset of its source masses sums to \(\frac12\). We now prove that this is equivalent to the original PARTITION instance.
The total mass of all original types is \(W/H<\frac12\), so a subset of mass \(\frac12\) must contain an additional type. It cannot contain both additional types, because their combined mass is
\[ \frac{H-W}{H}=1-\frac WH>\frac12. \]
Therefore it contains exactly one additional type. If \(I\subseteq\{1,\ldots,n\}\) denotes its original types, its mass equation is
\[ \sum_{i\in I}\frac{w_i}{H}+\frac{H-W}{2H}=\frac12. \]
Multiplication by \(2H\) gives
\[ 2\sum_{i\in I}w_i+H-W=H, \]
which is equivalent to \(\sum_{i\in I}w_i=W/2\).
Conversely, any subset of the original integers summing to \(W/2\), together with one additional type, has source mass \(\frac12\). Assign that subset to \(x\) and its complement to \(y\). Section 2 proves that the resulting coupling has zero reversal probability.
Thus the reduction preserves both yes- and no-instances, including instances with odd \(W\).
Let \(S\) be the bit length of the PARTITION instance and let \(B\) be the bit length of \(2H\). Then \(B=O(\log(W+1))=O(S)\). Every constructed mass has an encoding of \(O(B)\) bits.
The constructed parameters are
\[ \tau=n+2,\qquad \tau'=2,\qquad m=n+2. \]
Using explicit preference lists, the output length satisfies
\[ L=O\!\left((\tau^2+\tau'^2)\log m+\tau B\right). \]
Binary summation, constructing the dyadic masses, and writing the rankings take
\[ O\!\left(nB+(\tau^2+\tau'^2)\log m\right) \]
bit operations. This is polynomial in \(S\), so the construction is a polynomial-time many-one reduction.
For the restricted family in Section 2 with dyadic masses and two equal target masses, a certificate is simply the subset assigned to the first target type. Checking its mass takes \(O(\tau L+L)\) bit operations, including reading the input. Hence this restricted problem belongs to \(\mathrm{NP}\) and is \(\mathrm{NP}\)-complete. Exhaustive subset enumeration takes \(O(2^\tau\tau L+L)\) bit operations, or \(O(2^m mL+L)\) on the constructed instances.
For arbitrary societies, direct evaluation of the defining cubic polynomial uses \(O((\tau\tau')^3)\) arithmetic operations, at most \(O(m^6)\). This evaluation bound does not make minimizing it polynomial-time.
The continuous decision problem is \(\mathrm{NP}\)-hard; therefore a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\). The reduction succeeds because zero reversal itself forces source masses to remain unsplit, eliminating the fractional-coupling obstacle.
⟨structured verdict parsed — rendered above⟩
The continuous decision problem is correctly proved \(\mathrm{NP}\)-hard. The reduction directly addresses real couplings under the sampling convention in USER_TASK. There is one minor scope issue in the supplementary \(\mathrm{NP}\)-completeness claim.
Ranking each type strictly above all other types, with those other types tied, defines a complete weak order. It gives precisely
\[
b\succ_a c \iff b=a\text{ and }c\ne a.
\]
The corresponding target equivalence is also correct.
Conditional on the first draw having type pair \((a,a')\), the first reversal event requires the second draw to lie in row \(a\), outside column \(a'\), and the third draw to lie in column \(a'\), outside row \(a\). Independence therefore gives the stated product
\[
(\mu_a-\pi_{aa'})(\nu_{a'}-\pi_{aa'}).
\]
Exchanging the second and third draws gives the same probability for the other event. The events are disjoint because they require opposite strict comparisons.
Consequently, formula (1), including its factor of two, is correct. Conditioning on a cell of probability zero is unnecessary; equivalently, its contribution is zero. This introduces no gap.
Repeated type labels are allowed by the task. Thus comparisons involving different individuals of the same type do not invalidate this calculation.
The marginal constraints imply
\[
0\leq\pi_{aa'}\leq\min\{\mu_a,\nu_{a'}\},
\]
so every summand in (1) is nonnegative.
Under the explicitly stated assumption \(\mu_a<\nu_{a'}\), the factor \(\nu_{a'}-\pi_{aa'}\) is strictly positive. Hence each summand vanishes exactly when \(\pi_{aa'}=0\) or \(\pi_{aa'}=\mu_a\).
Positivity of every row mass then forces exactly one nonzero entry per row. Conversely, any assignment of whole rows satisfying the column marginals makes every summand zero.
Equation (4) follows correctly for two equal target masses and source masses strictly below one half. This argument covers all real couplings; there is no integrality assumption or rounding step.
The invoked theorem is the standard \(\mathrm{NP}\)-completeness of PARTITION for positive integers represented in binary. Its formulation matches the input used here. This theorem is also explicitly documented in [MIT’s PARTITION discussion](https://hardness.mit.edu/drafts/2022-12-15.pdf).
For a nonempty input, positivity gives \(W>0\). The smallest power of two strictly exceeding \(2W\) satisfies
\[
2W<H\leq4W.
\]
Every constructed mass is positive and dyadic. Their displayed sum is exactly one.
The required strict bound on source masses holds: \(w_i/H<1/2\), and
\[
0<\frac{H-W}{2H}<\frac12.
\]
Thus equation (4) applies to every constructed instance.
A subset of mass one half cannot consist solely of original types, since their total mass is below one half. It cannot contain both additional types, since their combined mass exceeds one half. It therefore contains exactly one additional type.
The displayed mass equation is equivalent to
\[
2\sum_{i\in I}w_i=W.
\]
This verifies both directions of the reduction. If \(W\) is odd, the equality is impossible because the left side is even, so odd-total no-instances are preserved as claimed.
The construction satisfies all input requirements, including nonempty supports, positive binary rational masses, complete weak orders including own types, and the permitted threshold \(q=0\).
The bound \(B=O(\log(W+1))=O(S)\) is valid. Both the numerators and denominators of constructed masses have \(O(B)\) bits.
With explicit preference lists, the stated output-size bound
\[
L=O\!\left((\tau^2+\tau'^2)\log m+\tau B\right)
\]
accounts for the alternative labels and masses. The stated construction time is polynomial in the PARTITION input length.
For the family satisfying equation (2), a subset is a complete certificate. Exact dyadic summation permits the stated \(O(\tau L+L)\) verification bound and the stated exhaustive-enumeration bound.
The \(O((\tau\tau')^3)\) general evaluation bound correctly counts arithmetic operations. It is not presented as a bit-complexity bound or as an optimization algorithm.
The opening says “This restricted problem is also” \(\mathrm{NP}\)-complete immediately after listing four restrictions. Those restrictions do not include \(\mu_a<1/2\). However, Section 4 establishes membership only for the narrower family from Section 2, which includes this additional condition.
The distinction matters to the certificate argument. Consider one source type of mass one and two target types of mass one half each, with the prescribed preferences. The source has no strict comparison between alternatives, so the unique coupling has zero reversal probability. Nevertheless, no subset of source masses sums to one half. This satisfies the four opening restrictions and shows why the subset certificate does not cover their full scope.
Minimum clarification: add \(\mu_a<1/2\) to the opening restrictions, or explicitly limit the supplementary NP-completeness assertion to the family satisfying that condition. The existing proof then supports the assertion without additional mathematics.
The main hardness conclusion stands. The proof also establishes NP-completeness for the explicitly analyzed narrower family. It does not establish NP membership for the unrestricted continuous problem, and does not claim to do so.
⟨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.