Browse › Theoretical computer science › 105 Perfect completeness for 2-to-1 games
Perfect completeness for 2-to-1 games
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Perfect completeness for 2-to-1 games (Lean scope note) (lean/docs/105.md, October 2026). The release's scope note states that the formalized result is the full Theorem 1.1 reduction from binary 3SAT (fixed rational δ, value 1 vs. at most δ, exact two-element fibers, explicit unweighted constraints, runtime in the input bit length) and links the Comparator statement
ComparatorChallenges/PerfectCompleteness.lean.
Related prior literature mentioned by others
- Yumou Fei, Dor Minzer and Shuo Wang, On the Hardness of 4-to-1 Games with Perfect Completeness (ECCC TR26-179, 14 Sep 2026; revised 8 Oct 2026). Proves the perfect-completeness 4-to-1 analogue at arbitrarily small soundness and is cited by the paper; Fortnow's exposition and Quanta compare it with the 2-to-1 result, including their shared consequence for coloring three-colorable graphs with any fixed number of colors.
Possibly relevant literature (found by the agent, not checked)
- Dinur, Mossel, Regev, Conditional Hardness for Approximate Coloring (arXiv:cs/0504062, 2005). Derives hardness of approximate coloring (chromatic number at most q vs. at least Q, for q ≥ 4) from Khot's 2-to-1 conjecture, which bears on the paper's coloring consequences in Section 1.3; the paper does not cite it.
Digests and expositions
- Prepared with Claude for Lance Fortnow, Perfect Completeness for 2-to-1 Games: An expository account of the proof (github.com/fortnow/AI-Papers, 15 Oct 2026; PDF). An expository rewrite aimed at complexity theorists covering the tree of function spaces, partition-valued questions, the three soundness stages and the three external black-box theorems; it states that its author did not run the Lean check. [AI-generated per source]
- Open Mathematics Courses, 2-to-1 games with perfect completeness (undated). A ten-lesson exposition of the proof with examples and solved exercises that treats three external theorems as named hypotheses and identifies itself as written and self-checked by Claude Opus 5.5 with independent review incomplete. [AI-generated per source]
News and blogs
- Ben Brubaker (Quanta Magazine), As AI Closed In on 'Unique Games' Proof, Researchers Raced to Beat the Machines (Quanta, 7 Oct 2026). Covers the race between the Fei–Minzer–Wang 4-to-1 paper and the OpenAI release, reporting that the release included a Lean-verified proof in an AI-generated manuscript that no independent experts had reviewed, and quotes Braverman and Minzer on AI-driven research.
- Gil Kalai, Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans (Combinatorics and more, 7 Oct 2026). Item 18 identifies the perfect-completeness 2-to-1 announcement separately from Unique Games and connects it to Kalai's 2018 discussion of the 2-to-2 Games Theorem and the perfect-completeness question.
Elsewhere
- Lance Fortnow: Exposition (written with Claude)
- VibeMathed: Problem record
- Emergent Mind: family 105
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Perfect-completeness-for-2-to-1-games-September-23-2026,
author = {{OpenAI}},
title = {{Perfect completeness for 2-to-1 games}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Perfect-completeness-for-2-to-1-games-September-23-2026/paper.pdf}{OAI:Perfect-completeness-for-2-to-1-games-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/105.md. The Lean statements have not been checked by people against the paper's claims.
Family 105: Perfect completeness for 2-to-1 games
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.
This is the only paper in this family.