Proves Khot's 2-to-1 Games Conjecture with perfect completeness: for every fixed rational \delta\in(0,1), it is NP-hard to distinguish satisfiable games from games whose optimum is at most δ, on explicit unweighted instances. The alphabet depends only on δ, and every right-hand label has exactly two preimages under each constraint map. (Lean)
Manuscript
Perfect completeness for 2-to-1 games
September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:Perfect-completeness-for-2-to-1-games-September-23-2026}
We prove the 2-to-1 Games Conjecture with perfect completeness. For every fixed rational \delta\in(0,1), it is NP-hard to distinguish satisfiable 2-to-1 games from games of value at most δ, with a fixed alphabet and an explicitly listed unweighted multiset of constraints.
Result 105 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Agora members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md