Answer: \(\mathrm{NP\text{-}complete}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSUBELECTION ISOMORPHISM is NP-com- plete and W[1]-hard with respect to the size of the smaller election.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite candidate sets \(A,B\) with \(|A|\le |B|\), rational distributions \(\mu\) and \(\nu\) over complete rankings of \(A\) and \(B\), and rational \(\lambda\in(0,1]\), does there exist \(S\subseteq B\) with \(|S|=|A|\), a bijection \(\sigma:A\to S\), and masses \(0\le x_\rho\le\nu_\rho\) such that \(\sum_\rho x_\rho=\lambda\) and, for every ranking \(\pi\) of \(A\), \(\sum_{\rho:\,\sigma^{-1}(\rho|_S)=\pi}x_\rho=\lambda\mu_\pi\)?
An instance explicitly lists the positive rational masses of distributions \(\mu\) on complete rankings of \(A\) and \(\nu\) on complete rankings of \(B\), together with rational \(\lambda\in(0,1]\); both distributions have total mass \(1\).
For a ranking \(\rho\) of \(B\) and \(S\subseteq B\), \(\rho|_S\) is its restriction to \(S\). For a bijection \(\sigma:A\to S\), \(\sigma^{-1}(\rho|_S)\) is the ranking of \(A\) obtained by replacing each \(s\in S\) with \(\sigma^{-1}(s)\).
Continuous Subelection Isomorphism asks whether there are \(S\subseteq B\) with \(|S|=|A|\), a bijection \(\sigma:A\to S\), and \(0\le x_\rho\le\nu_\rho\) such that \(\sum_\rho x_\rho=\lambda\) and \(\sum_{\rho:\,\sigma^{-1}(\rho|_S)=\pi}x_\rho=\lambda\mu_\pi\) for every ranking \(\pi\) of \(A\).
Is Continuous Subelection Isomorphism solvable in polynomial time, or is it NP-hard?
For finite ordinal elections, Subelection Isomorphism is NP-complete and \(\mathrm{W}[1]\)-hard parameterized by the size of the smaller election.
Continuous Subelection Isomorphism is \(\mathrm{NP}\)-complete. It remains \(\mathrm{NP}\)-hard under all of the following restrictions:
Thus the continuous choice of the variables \(x_\rho\) does not make the problem polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
A choice of \(S\subseteq B\) and a bijection \(\sigma:A\to S\) is equivalently an injection \(\sigma:A\hookrightarrow B\), with \(S=\sigma(A)\).
For such an injection and a ranking \(\pi\) of \(A\), define its available capacity by
\[ c_\sigma(\pi) = \sum_{\rho:\,\sigma^{-1}(\rho|_{\sigma(A)})=\pi}\nu_\rho. \]
For a fixed injection \(\sigma:A\hookrightarrow B\), suitable variables \(x_\rho\) exist if and only if
\[ c_\sigma(\pi)\geq \lambda\mu_\pi \]
for every ranking \(\pi\) in the support of \(\mu\).
Suppose first that feasible variables \(x_\rho\) exist. For every \(\pi\),
\[ \lambda\mu_\pi = \sum_{\rho:\,\sigma^{-1}(\rho|_{\sigma(A)})=\pi}x_\rho \leq \sum_{\rho:\,\sigma^{-1}(\rho|_{\sigma(A)})=\pi}\nu_\rho = c_\sigma(\pi). \]
This proves necessity.
Conversely, suppose the displayed inequalities hold. For each \(\pi\) in the support of \(\mu\), consider the fiber
\[ F_\pi = \{\rho:\sigma^{-1}(\rho|_{\sigma(A)})=\pi\}. \]
The fibers are pairwise disjoint. Their total available mass satisfies
\[ \sum_{\rho\in F_\pi}\nu_\rho = c_\sigma(\pi) \geq \lambda\mu_\pi. \]
Therefore one can choose, independently inside each fiber, numbers \(0\leq x_\rho\leq\nu_\rho\) whose sum is exactly \(\lambda\mu_\pi\). For example, process the rankings of \(F_\pi\) in any order and take as much remaining required mass as possible from each ranking. Set \(x_\rho=0\) on fibers corresponding to rankings outside the support of \(\mu\).
Then all required fiber equalities hold, and
\[ \sum_\rho x_\rho = \sum_\pi\lambda\mu_\pi = \lambda, \]
because \(\mu\) has total mass \(1\). Hence the constructed variables are feasible. \(\square\)
When \(\lambda=1\), feasibility for \(\sigma\) is equivalent to exact equality between \(\mu\) and the distribution obtained by restricting every ranking in \(\nu\) to \(\sigma(A)\) and relabeling through \(\sigma^{-1}\).
Indeed, if \(x_\rho\leq\nu_\rho\) and
\[ \sum_\rho x_\rho=1=\sum_\rho\nu_\rho, \]
then
\[ \sum_\rho(\nu_\rho-x_\rho)=0. \]
Every summand is nonnegative, so \(x_\rho=\nu_\rho\) for every \(\rho\).
A certificate is an injection \(\sigma:A\hookrightarrow B\). Its encoding has polynomial length.
For each explicitly listed ranking \(\rho\) in the support of \(\nu\), one can compute the induced ranking
\[ \sigma^{-1}(\rho|_{\sigma(A)}) \]
in polynomial time and add \(\nu_\rho\) to the corresponding capacity. Lemma 1 then reduces verification to exact comparisons of rational numbers.
Adding and comparing polynomially many binary-encoded rationals takes polynomial time: the numerator and denominator bit lengths grow at most linearly in the total input bit length. Hence Continuous Subelection Isomorphism belongs to \(\mathrm{NP}\).
We reduce from Permutation Pattern Matching.
An instance consists of a pattern permutation
\[ P=(p_1,\ldots,p_k) \]
of \(\{1,\ldots,k\}\) and a text permutation
\[ T=(t_1,\ldots,t_n) \]
of \(\{1,\ldots,n\}\), where \(k\leq n\). The question is whether there are indices
\[ 1\leq i_1<\cdots<i_k\leq n \]
such that, for every \(r,s\in\{1,\ldots,k\}\),
\[ p_r<p_s \quad\Longleftrightarrow\quad t_{i_r}<t_{i_s}. \]
Permutation Pattern Matching is \(\mathrm{NP}\)-complete by Bose, Buss, and Lubiw, [“Pattern matching for permutations”](https://www.sciencedirect.com/science/article/pii/S0020019097002093).
First suppose that neither \(P\) nor \(T\) is the identity permutation.
Let
\[ A=\{a_1,\ldots,a_k\}, \qquad B=\{b_1,\ldots,b_n\}. \]
Define two rankings of \(A\). The position ranking is
\[ \alpha^{\mathrm{pos}} = a_1\succ a_2\succ\cdots\succ a_k. \]
The value ranking orders the candidates by increasing value of the corresponding pattern entry:
\[ \alpha^{\mathrm{val}} = a_{P^{-1}(1)} \succ a_{P^{-1}(2)} \succ\cdots\succ a_{P^{-1}(k)}. \]
Equivalently, \(a_r\) precedes \(a_s\) in \(\alpha^{\mathrm{val}}\) exactly when \(p_r<p_s\).
Similarly, define rankings of \(B\) by
\[ \beta^{\mathrm{pos}} = b_1\succ b_2\succ\cdots\succ b_n \]
and
\[ \beta^{\mathrm{val}} = b_{T^{-1}(1)} \succ b_{T^{-1}(2)} \succ\cdots\succ b_{T^{-1}(n)}. \]
Thus \(b_i\) precedes \(b_j\) in \(\beta^{\mathrm{val}}\) exactly when \(t_i<t_j\).
Set
\[ \mu_{\alpha^{\mathrm{pos}}}=\frac13, \qquad \mu_{\alpha^{\mathrm{val}}}=\frac23, \]
and
\[ \nu_{\beta^{\mathrm{pos}}}=\frac13, \qquad \nu_{\beta^{\mathrm{val}}}=\frac23. \]
Finally, set \(\lambda=1\).
Because \(P\) and \(T\) are not identity permutations, the two rankings in each distribution are distinct. The construction has polynomial size.
The permutation \(P\) occurs in \(T\) if and only if the constructed Continuous Subelection Isomorphism instance is feasible.
Suppose there are indices
\[ i_1<\cdots<i_k \]
witnessing an occurrence of \(P\) in \(T\). Define
\[ \sigma(a_r)=b_{i_r}. \]
Since the indices are strictly increasing, restricting \(\beta^{\mathrm{pos}}\) to \(\sigma(A)\) gives
\[ b_{i_1}\succ\cdots\succ b_{i_k}. \]
Consequently,
\[ \sigma^{-1}(\beta^{\mathrm{pos}}|_{\sigma(A)}) = \alpha^{\mathrm{pos}}. \]
For every \(r,s\), the occurrence condition gives
\[ a_r\text{ precedes }a_s\text{ in }\alpha^{\mathrm{val}} \]
if and only if
\[ p_r<p_s \]
if and only if
\[ t_{i_r}<t_{i_s}, \]
if and only if
\[ b_{i_r}\text{ precedes }b_{i_s}\text{ in }\beta^{\mathrm{val}}. \]
Hence
\[ \sigma^{-1}(\beta^{\mathrm{val}}|_{\sigma(A)}) = \alpha^{\mathrm{val}}. \]
Taking \(x_\rho=\nu_\rho\) therefore produces exactly the target distribution \(\mu\), so the election instance is feasible.
Suppose the election instance is feasible. Since \(\lambda=1\), Corollary 2 gives
\[ x_{\beta^{\mathrm{pos}}}=\frac13, \qquad x_{\beta^{\mathrm{val}}}=\frac23. \]
Write
\[ \gamma^{\mathrm{pos}} = \sigma^{-1}(\beta^{\mathrm{pos}}|_{\sigma(A)}) \]
and
\[ \gamma^{\mathrm{val}} = \sigma^{-1}(\beta^{\mathrm{val}}|_{\sigma(A)}). \]
Equality with the target distribution says
\[ \frac13\delta_{\gamma^{\mathrm{pos}}} + \frac23\delta_{\gamma^{\mathrm{val}}} = \frac13\delta_{\alpha^{\mathrm{pos}}} + \frac23\delta_{\alpha^{\mathrm{val}}}, \]
where \(\delta_\gamma\) denotes a unit mass at ranking \(\gamma\).
Because \(\alpha^{\mathrm{pos}}\neq\alpha^{\mathrm{val}}\), the right-hand side assigns mass exactly \(2/3\) to \(\alpha^{\mathrm{val}}\). On the left, mass \(2/3\) at a ranking is possible only when
\[ \gamma^{\mathrm{val}}=\alpha^{\mathrm{val}} \quad\text{and}\quad \gamma^{\mathrm{pos}}\neq\alpha^{\mathrm{val}}. \]
The remaining mass \(1/3\) must then be at \(\alpha^{\mathrm{pos}}\). Therefore
\[ \gamma^{\mathrm{pos}}=\alpha^{\mathrm{pos}}, \qquad \gamma^{\mathrm{val}}=\alpha^{\mathrm{val}}. \]
Write
\[ \sigma(a_r)=b_{i_r}. \]
Equality of the position rankings implies
\[ i_1<\cdots<i_k. \]
Equality of the value rankings implies, for all \(r,s\),
\[ p_r<p_s \quad\Longleftrightarrow\quad t_{i_r}<t_{i_s}. \]
Thus \(i_1,\ldots,i_k\) witness an occurrence of \(P\) in \(T\). \(\square\)
The preceding construction assumes both permutations are nonidentity so that both distributions have two distinct support rankings. The exceptional cases can be handled in polynomial time while preserving the many-one reduction.
If \(P\) is the identity permutation, then \(P\) occurs in \(T\) exactly when \(T\) has an increasing subsequence of length \(k\). This can be decided, for example, by the recurrence
\[ L_j = 1+\max\{L_i:i<j\text{ and }t_i<t_j\}, \]
with the maximum over the empty set taken as \(0\). The answer is yes exactly when \(\max_jL_j\geq k\).
If \(P\) is nonidentity and \(T\) is identity, the answer is no, because every subsequence of \(T\) is increasing.
After deciding either exceptional case, output a fixed yes-instance or fixed no-instance. These can also be chosen with \(\lambda=1\), exactly two rankings per distribution, and masses \(1/3\) and \(2/3\):
Thus the reduction is defined on every Permutation Pattern Matching instance and preserves the answer.
The reduction proves \(\mathrm{NP}\)-hardness even at \(\lambda=1\) with two constant-weight support rankings in each distribution. Together with membership in \(\mathrm{NP}\), this establishes that Continuous Subelection Isomorphism is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes that Continuous Subelection Isomorphism is \(\mathrm{NP}\)-complete, including the claimed restricted hardness. The capacity characterization, membership argument, reduction from Permutation Pattern Matching, both directions of the reduction, and exceptional identity cases are all valid.
No substantive gaps or false statements were found.
Lemma 1 is correct.
For a fixed injection \(\sigma\), every ranking of \(B\) belongs to exactly one fiber \(F_\pi\), determined by its restricted and relabeled ranking. Thus the fibers are disjoint.
Necessity follows directly from \(x_\rho\leq\nu_\rho\). For sufficiency, the capacity inequality for each supported \(\pi\) permits selecting exactly \(\lambda\mu_\pi\) mass within its fiber. Because the fibers are disjoint, these selections do not interfere. Setting all other variables to zero satisfies the equations for unsupported rankings as well. Finally,
\[ \sum_\rho x_\rho=\lambda\sum_\pi\mu_\pi=\lambda. \]
No assumption about integrality or indivisibility of masses is being made.
Corollary 2 is correct. Since every difference \(\nu_\rho-x_\rho\) is nonnegative and their finite sum is zero, each difference is zero. Hence \(x_\rho=\nu_\rho\) for every ranking. Feasibility therefore reduces to equality of the target distribution and the restricted, relabeled source distribution.
The injection is a polynomial-size certificate. Restricting each explicitly listed source ranking, relabeling it, accumulating rational capacities, and comparing those capacities with \(\lambda\mu_\pi\) can all be performed in polynomial time.
The rational-arithmetic claim is also valid: even if denominators are multiplied rather than reduced optimally, their total bit length is bounded by the sum of the input denominator lengths, hence polynomial in the explicit input size.
The stated definition of Permutation Pattern Matching agrees with the cited source problem. Bose, Buss, and Lubiw do prove the general problem \(\mathrm{NP}\)-complete, as confirmed by the [publisher’s abstract](https://www.sciencedirect.com/science/article/pii/S0020019097002093).
When \(P\) is nonidentity, \(\alpha^{\mathrm{pos}}\) and \(\alpha^{\mathrm{val}}\) are distinct. Likewise, when \(T\) is nonidentity, the two source rankings are distinct. Therefore both distributions have exactly two support rankings with the claimed masses.
The construction is polynomial in the permutation input sizes.
Given an occurrence at indices \(i_1<\cdots<i_k\), the injection \(\sigma(a_r)=b_{i_r}\) sends the restricted position ranking to \(\alpha^{\mathrm{pos}}\).
The pattern-occurrence condition gives exactly the pairwise comparisons needed for the restricted value ranking to become \(\alpha^{\mathrm{val}}\). Since \(\lambda=1\), taking \(x_\rho=\nu_\rho\) produces \(\mu\). This implication is complete.
Because \(\lambda=1\), both source atoms retain their full masses. The target atoms are distinct and have unequal masses \(1/3\) and \(2/3\).
The equality of atomic distributions forces the \(2/3\)-weighted value ranking to map to \(\alpha^{\mathrm{val}}\) and the \(1/3\)-weighted position ranking to map to \(\alpha^{\mathrm{pos}}\). A collision of the two induced source rankings would create a mass-\(1\) atom and therefore cannot satisfy the target distribution.
Writing \(\sigma(a_r)=b_{i_r}\), equality of position rankings gives \(i_1<\cdots<i_k\), while equality of value rankings gives
\[ p_r<p_s\quad\Longleftrightarrow\quad t_{i_r}<t_{i_s} \]
for every \(r,s\). These indices are therefore a valid pattern occurrence.
The cases are exhaustive:
Using polynomial-time preprocessing on these easy subfamilies and returning fixed yes- or no-instances is legitimate in a polynomial-time many-one reduction.
The fixed yes-instance is plainly feasible. In the fixed no-instance, the unequal weights force ranking \(123\) to correspond to \(123\). This uniquely fixes the bijection by rank position, under which the reverse ranking \(321\) remains \(321\), not \(213\). Hence the fixed no-instance is indeed infeasible.
The proof establishes both membership in \(\mathrm{NP}\) and \(\mathrm{NP}\)-hardness under all stated restrictions. It fully resolves the target question.
⟨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.