Theorem · version 1
Computing a linear order minimizing the sum of Kendall-tau distances to exactly three strict complete ballots is NP-hard.
Proved
Computing a minimizing order is NP-hard; decision NP-completeness is a distinct classification.
Kemeny Rank Aggregation is NP-Hard for Three Voters · Sections 1 and 6 →
Source dated Jul 28, 2026 · Observed Oct 14, 2026
In this problem · publication v5 · Selected context
Alternative answer · Proved
A consensus optimizer would also answer score-threshold questions; the two tasks have different complexity classifications.
NP-completeness concerns the decision language; optimization is described as NP-hard.
Proved · version 1
Given exactly three strict complete linear orders π₁, π₂, π₃ on a finite set A and an integer B, deciding whether there exists an order π with is NP-complete.
Scope: KT counts unordered pairs whose relative orders disagree. The paper’s majority-margin threshold b is translated by the computable profile constant ∑{a,b} min(n_ab,n_ba).
Proved · version 1
Computing a linear order minimizing the sum of Kendall-tau distances to exactly three strict complete ballots is NP-hard.
Scope: This is a function/optimization task; NP-completeness is stated for the threshold decision language. Worst-case hardness does not prove P ≠ NP.
Relationship not independently reviewed.
Connection in Kemeny rank aggregation for three voters →Relationship not independently reviewed. This concerns its use in this problem.
A polynomial reduction from SIMPLE MAX CUT, using a majority tournament realizable by exactly three complete ballots, proves decision NP-completeness.
paraphrase · Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.
Computing an optimum is NP-hard for three voters. The paper also explains extensions to every fixed voter count at least three and recalls the polynomial-time two-voter case.
paraphrase · Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.
The total Kendall-tau score differs from the majority-disagreement score by a ballot-dependent constant; they have the same minimizers. Three voters was the remaining boundary question.
paraphrase · Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.
Dominik Peters · Preprint · Publication date Jul 28, 2026
Source-reported results and external checks are separate from independent OpenMath assessment.
Source revision: v1. Observed Oct 14, 2026.
Peters credits GPT-5.6 Sol Ultra with finding the reduction, Claude Fable 5 with part of the simplification, and his own mathematical simplification and manuscript writing.
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Computing a minimizing order is NP-hard; decision NP-completeness is a distinct classification.
Source dated Jul 28, 2026 · Observed Oct 14, 2026 · Source passage →