Answer: \(\mathrm{NP}\)-complete
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate\kkemeny is $\np$-complete even for $k=2$ and elections that are both SP and GS/bal.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), an axis \(\lhd\), a balanced group-separating tree \(\mathcal T\), and a rational mass distribution \(\mu\) over \(\mathcal D=\mathrm{SP}(\lhd)\cap\mathrm{GS}_{\mathrm{bal}}(\mathcal T)\), decide whether there exist \(r_1,r_2\in\mathcal L(C)\) such that \(\sum_{v\in\mathcal D}\mu_v\min\{\mathrm{swap}(v,r_1),\mathrm{swap}(v,r_2)\}\le q\), for rational \(q\).
Given a candidate set \(C\) with \(m\ge 2\), let \(\mathcal L(C)\) be its strict linear orders. The input includes a single-peaked axis \(\lhd\) and a rooted, ordered binary tree \(\mathcal T\) whose leaves are bijectively labeled by \(C\); every level except possibly the last is completely filled.
A ranking belongs to \(\mathrm{GS}_{\mathrm{bal}}(\mathcal T)\) if it is obtained by independently reversing the order of the two children at any internal nodes and then reading the leaves from left to right. Set \(\mathcal D=\mathrm{SP}(\lhd)\cap\mathrm{GS}_{\mathrm{bal}}(\mathcal T)\), where \(\mathrm{SP}(\lhd)\) is the single-peaked domain on the supplied axis. Write \(\mathrm{swap}\) for Kendall tau distance.
A society is given by its support: a list \(S\subseteq\mathcal D\) of \(\tau\) distinct types with positive binary rational masses \(\mu_v\), satisfying \(\sum_{v\in S}\mu_v=1\). Here \(\tau\) is the support size, not the number of possible rankings. The threshold is \(q\in\mathbb Q\), encoded in binary; \(L\) is the total input bit length.
The decision problem asks whether there exist two distinct rankings \(r_1,r_2\in\mathcal L(C)\) satisfying \(\sum_{v\in S}\mu_v\min\{\mathrm{swap}(v,r_1),\mathrm{swap}(v,r_2)\}\le q\). The centers need not belong to \(\mathcal D\); equal distances require no tie-breaking.
Is this decision problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite voter lists, deciding whether the \(2\)-Kemeny score is at most a given integer is NP-complete even when all votes are simultaneously single-peaked on one axis and consistent with one balanced group-separating tree.
The decision problem is \(\mathrm{NP}\)-complete. In particular, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
Use the finite-list \(\mathrm{NP}\)-completeness result stated in the question. Its hardness construction explicitly provides a common single-peaked axis and a balanced binary group-separating tree. The definitions of tree consistency and balance agree with those in this task. Consequently, supplying these witnesses preserves the hardness. See [Theorem 3.1 and its construction](https://arxiv.org/html/2509.15812v1#S3.SS1).
Thus we start with a hard instance consisting of a candidate set \(C\), an explicit voter list \(V=(v_1,\ldots,v_n)\), its axis \(\lhd\), its balanced tree \(\mathcal T\), and an integer threshold \(K\). Here \(n\geq 1\), and every vote belongs to \(\mathrm{SP}(\lhd)\cap\mathrm{GS}_{\mathrm{bal}}(\mathcal T)\). The question is whether two unrestricted centers achieve total distance at most \(K\).
Let \(S\) be the set of distinct rankings occurring in \(V\). For each \(v\in S\), define its multiplicity and mass by
\[ n_v=\bigl|\{i:v_i=v\}\bigr|, \qquad \mu_v=\frac{n_v}{n}. \]
Set the new threshold to \(q=K/n\), and retain \(C,\lhd,\mathcal T\).
Every mass is a positive rational, and \(\sum_{v\in S}\mu_v=1\). Removing duplicate occurrences does not change any ranking, so the required domain condition remains satisfied.
For every pair of centers \(r_1,r_2\in\mathcal L(C)\), grouping identical votes gives the exact identity
\[ \begin{aligned} \sum_{v\in S}\mu_v \min\{\mathrm{swap}(v,r_1),\mathrm{swap}(v,r_2)\} &= \frac1n\sum_{v\in S}n_v \min\{\mathrm{swap}(v,r_1),\mathrm{swap}(v,r_2)\}\\ &= \frac1n\sum_{i=1}^{n} \min\{\mathrm{swap}(v_i,r_1),\mathrm{swap}(v_i,r_2)\}. \end{aligned} \]
Since \(n>0\), the left-hand side is at most \(q=K/n\) exactly when the original total is at most \(K\). Ties between the centers do not affect this identity.
The transformation has polynomial cost. Distinct rankings and their multiplicities can be computed by sorting the explicit voter list. Moreover, \(\tau=|S|\leq n\), each mass uses \(O(\log n)\) bits for its numerator and denominator, and encoding \(K/n\) requires only the encoding length of \(K\) plus \(O(\log n)\) bits. Hence all output parameters, including \(L\), are polynomially bounded in the source input length.
This proves \(\mathrm{NP}\)-hardness.
If the source convention permits one center or two identical centers, its feasibility question is still equivalent to the distinct-center version here.
Indeed, because \(m\geq2\), for every ranking \(r\) there exists another ranking \(s\neq r\). For every vote \(v\),
\[ \min\{\mathrm{swap}(v,r),\mathrm{swap}(v,s)\} \leq \mathrm{swap}(v,r). \]
Thus a feasible single center can be extended to two distinct centers without increasing the score. Conversely, two distinct centers are admissible whenever at most two centers are permitted. Therefore the reduction works under either convention.
A certificate consists of two distinct permutations \(r_1,r_2\) of \(C\), requiring \(O(m\log m)\) bits. Their validity and distinctness are directly checkable.
Kendall tau distance counts candidate pairs whose relative orders disagree. Comparing all pairs computes each distance in \(O(m^2)\) time. Therefore all distances needed for verification take \(O(\tau m^2)\) time.
The weighted comparison can also be performed exactly in polynomial time. Write the input rationals as \(\mu_v=a_v/b_v\) and \(q=A/B\), with positive denominators, and let
\[ d_v=\min\{\mathrm{swap}(v,r_1),\mathrm{swap}(v,r_2)\}, \qquad D=B\prod_{v\in S}b_v. \]
The verifier checks the integer inequality
\[ \sum_{v\in S}a_vd_v\frac{D}{b_v} \leq A\frac{D}{B}. \]
The bit length of \(D\) is at most the sum of the input denominator bit lengths, hence \(O(L)\). Also, \(0\leq d_v\leq\binom m2\). All integers in this calculation therefore have polynomial bit length, so exact verification takes polynomial time.
Together with the reduction, this establishes \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task correctly: the support-encoded decision problem is \(\mathrm{NP}\)-complete. No major or minor mathematical issues were found.
The prover invokes precisely the finite-list hardness result supplied in USER_TASK, rather than hardness for either domain separately.
The additional requirement that the axis and tree be supplied needs verification: an existence-only restriction would not automatically provide those witnesses in polynomial time. The cited construction specifies a common axis and a balanced binary tree for the constructed votes. Its definitions of tree consistency and balance match the task, and its centers range over all strict rankings. Thus supplying the witnesses preserves the reduction. See [Theorem 3.1, Section 2.2, and the construction](https://arxiv.org/html/2509.15812v1#S3.SS1).
The source instances used here have a nonempty voter list and at least two candidates, as required for normalization and the distinct-center argument.
Assessment: The cited hardness result applies with the required hypotheses.
For each distinct source vote \(v\), its multiplicity \(n_v\) is a positive integer. Since the source list contains \(n>0\) votes, the proposed mass \(\mu_v=n_v/n\) is a valid positive binary-encoded rational.
The multiplicities sum to \(n\), so the masses sum to \(1\). Removing duplicate occurrences preserves membership in the supplied intersection domain. No new rankings are introduced.
Assessment: The transformation produces a valid target instance.
For every fixed pair of unrestricted centers, all occurrences of a particular vote have exactly the same distance to each center. Grouping these occurrences therefore gives the displayed identity: the target weighted score equals the source total score divided by \(n\).
Because \(n>0\), comparison with \(q=K/n\) preserves the inequality in both directions. The identity holds for every center pair, so it preserves the existential feasibility question.
Equal distances introduce no ambiguity: both objectives use the minimum distance, without requiring an assignment or tie-breaking rule.
Assessment: The reduction preserves yes-instances and no-instances exactly.
The source voter list is explicit. Consequently, sorting its rankings and counting duplicates takes polynomial time in the source input length.
The bounds \(\tau\leq n\) and \(1\leq n_v\leq n\) justify the stated encoding bounds for every mass. Encoding \(K/n\) requires polynomially many bits, including when \(K\) is negative or has large binary length. Reducing fractions, if required by the encoding convention, does not increase their size.
The candidate set, axis, and tree are retained. The complete target instance therefore has polynomial size and can be constructed in polynomial time.
Assessment: This is a polynomial-time many-one reduction.
The prover correctly handles source conventions allowing either at most two centers or repeated centers.
When a feasible solution uses only one ranking \(r\), the assumption \(m\geq2\) ensures that another ranking \(s\neq r\) exists. Adding \(s\) cannot increase any voter’s minimum distance. Conversely, a pair of distinct centers is admissible under the more permissive convention.
If the source already requires exactly two distinct rankings, no adjustment is necessary.
Assessment: The distinctness requirement does not invalidate the reduction.
Two permutations give a polynomial-size certificate. Their validity and distinctness can be checked directly.
Counting disagreeing candidate pairs computes each Kendall tau distance correctly. The resulting \(O(\tau m^2)\) distance computation is polynomial.
For the rational comparison, all denominators are positive. The proposed common denominator \(D=B\prod_{v\in S}b_v\) is therefore positive and divisible by every required denominator. Multiplying the score inequality by \(D\) preserves its direction and produces exactly the displayed integer inequality.
The bit length of \(D\) is bounded by the total denominator encoding length. Numerators, distances, products, and the final sum also have polynomial bit length. In particular, summing \(\tau\) terms adds at most a logarithmic dependence on \(\tau\) to their bit length. Exact verification is consequently polynomial.
The task guarantees valid structured inputs; the verifier need not establish that the proposed centers belong to the domain.
Assessment: Membership in \(\mathrm{NP}\) is established.
The proof establishes both \(\mathrm{NP}\)-hardness and membership in \(\mathrm{NP}\). It respects the support representation, binary rational encoding, supplied structural witnesses, unrestricted centers, and distinctness requirement. No additional clarification 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.