Theorem · version 1
For every fixed integer r ≥ 3, minimizing total Kendall-tau disagreement for r 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 v1 · Selected context
Related result · Proved
Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v5
Related result · Proved
Relationship not independently reviewed. This concerns its use in this problem.
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.
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 →