Theorem 1; Sections 1–6, especially the MAX CUT reduction and three-ballot realization.
Source-reported results and external checks are separate from independent OpenMath assessment.
The exact passages cited in OpenMath. Each passage identifies how its wording was recorded.
A polynomial reduction from SIMPLE MAX CUT, using a majority tournament realizable by exactly three complete ballots, proves decision NP-completeness.
Passage ID: kemeny-three-voters:entry:decision:v1
Source item: decision
Source record: kemeny-three-voters:source:paper:v1
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.
Passage ID: kemeny-three-voters:entry:implications:v1
Source item: implications
Source record: kemeny-three-voters:source:paper:v1
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.
Passage ID: kemeny-three-voters:entry:question:v1
Source item: question
Source record: kemeny-three-voters:source:paper:v1
Explicit citations in versioned problem publications. A citation records a use; it does not confer proof or independent verification.
Problem publication v5
Source assessment
Proved
Three-voter decision NP-completeness proved in the preprint
Strict complete ballots, unbounded number of alternatives, integer score threshold.
Source date Jul 28, 2026 · Observed Oct 14, 2026
Construction
Three ballots with a cyclic majority
Proof explanation
From a cut threshold to a ranking threshold
Source assessment
Proved
Optimization hardness and fixed-voter consequences
Computing a minimizing order is NP-hard; decision NP-completeness is a distinct classification.
Source date Jul 28, 2026 · Observed Oct 14, 2026
Source assessment
Proved
Optimization hardness and fixed-voter consequences
Computing a minimizing order is NP-hard; decision NP-completeness is a distinct classification.
Source date Jul 28, 2026 · Observed Oct 14, 2026
Source assessment
Proved
Two-voter baseline recalled
Either input order minimizes the total Kendall-tau score for two voters.
Source date Jul 28, 2026 · Observed Oct 14, 2026
Connection
A consensus optimizer would also answer score-threshold questions; the two tasks have different complexity classifications.
History
A three-ballot reduction is published
Question
Kemeny rank aggregation for three voters
Further reading
Follow both directions of the reduction and the three-ballot realization.
Further reading
Read the definition, score translation and original three-list question.
Recorded authorship
Dominik Peters
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.
OpenMath source records preserve exact citations. Observation dates order these records; they do not establish the latest upstream paper or proof.
Kemeny Rank Aggregation is NP-Hard for Three Voters
Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.
Source terms ↗