Theoretical computer science · Jul 28, 2026
Kemeny aggregation for three voters
A MAX CUT reduction establishes NP-completeness of the decision version and hardness of the optimization problem.
Scope and what remains
Three voters is the new boundary; hardness for larger even numbers was already known. NP-hardness is not a proof that P≠NP.
Contributors
Dominik Peters; reduction found by GPT-5.6 Sol Ultra and simplified in part with Claude Fable 5.
AI systems: GPT-5.6 Sol Ultra, Claude Fable 5