Kemeny Rank Aggregation for Three Voters

Precise statement

Is computing a Kemeny-optimal aggregate ranking NP-hard when the input consists of exactly three complete rankings? Hardness was known for every even $n \ge 4$; three voters was the minimal open case, and $n = 2$ is polynomial-time solvable.

The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement fidelity, correctness, priority, or novelty.

What AI did

GPT-5.6 Sol Ultra, Claude Fable 5

GPT-5.6 Sol Ultra found the reduction from MAX CUT; Claude Fable 5 helped simplify parts of it. Together with earlier results, every fixed number of voters $n \ge 3$ is now hard.

Provider: OpenAI / Anthropic · Prompt public: unknown · Independence: unknown

Verification boundary

lean verified statement audited

The reduction is Lean-checked, alongside an author-written arXiv preprint.

Correctness: supported · statement fidelity: audited · peer review: none

Timeline

1. 2026-07-28

   arXiv:2607.25540 - Kemeny rank aggregation is NP-hard for three voters

   VibeMathed reports this item as resolved. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.

Known method families

argument (source-reported)

Source-reported tools: argument.

Independent: unknown · difference confidence: 0

What remains uncertain

VibeMath has not independently audited the mathematical statement, proof, or novelty claim.

• VibeMath has not independently verified the mathematical claim.
• AI-attempt independence and training-data exposure are unknown unless explicitly documented.
• VibeMath has not independently audited the mathematical statement, proof, or novelty claim.