Unique games conjecture
Is approximating Unique Games NP-hard?
Summary
AI-assisted claims
The Unique Games Theorem
“We prove the Unique Games Conjecture. For every fixed ε, δ ∈ (0, 1/2), we give a deterministic polynomial-time reduction from 3SAT to Unique Games over a fixed finite alphabet, with completeness at least 1 − ε and soundness at most δ.”
- By
- OpenAI
- AI involvement
- This repository contains mathematical manuscripts and supporting proof artifacts produced by an internal OpenAI model.
- Model
- an unreleased internal OpenAI model, as stated
- Where
- openai/math repository
- Formal proof
- Lean 4, published by the source
- Repository
- openai/math at 4eaee87 · read 21 Nov 2026
- Source last read
- 14 Oct 2026
Checks
2 responses
- 07 Oct 2026 · Response · Scott Aaronson: “Or at least, we’re pretty sure that it’s a proof! There’s a Lean certificate, as there are for some of the other 372 breakthrough results (not all of them). But it also appears that no human has understood just about any of these proofs yet; the race to do so has just started.” Source
- 07 Oct 2026 · Response · Lance Fortnow: “Now these proofs haven't been fully verified but if they hold up, we've seen more progress in theoretical computer science in the last 24 hours than in the previous three decades combined!” Source
Claims as their sources state them. Listing a claim is not a check by Papex; the status stays the source’s.
Why it is open
A unique game is a constraint satisfaction problem. Each variable receives a label from a fixed finite set, and each constraint joins two variables by a one-to-one map, so that the label of one determines the label of the other [6]. When every constraint can be satisfied, a satisfying labelling is easy to find: try each label for one variable and propagate it along the constraints [6]. Subhash Khot's conjecture of 2002 concerns the nearly satisfiable case. For every ε, δ > 0 there should be a label set, of size depending on ε and δ, for which it is NP-hard to tell instances in which a 1 − ε fraction of the constraints can be satisfied from instances in which no labelling satisfies more than a δ fraction [2, 6]. An equivalent form uses linear equations of the form x − y = c modulo a number q, each in two variables [3].
NP-hard means that a polynomial-time algorithm separating the two cases would yield one for satisfiability, and hence P = NP [6] (see the Papex page P versus NP). A resolution is therefore either a proof of this hardness for every ε and δ, or an algorithm good enough to separate the cases and so disprove the conjecture [6]. Khot has also pointed to a third possibility: the problem might be neither in P nor NP-complete [6].
Known algorithms constrain any proof. A result of Sanjeev Arora, Boaz Barak and David Steurer implies that if 3SAT needs fully exponential time, any reduction from 3SAT to Unique Games would have to run in time n^(1/ε^0.01), where ε is the completeness parameter [8] (see the Papex page Exponential time hypothesis). The Wikipedia list on which this page's status rests counts a problem as unsolved "when no solution is known or when experts in the field disagree about proposed solutions" [15].
What is known
Consequences (1995–2008). In 1995 Michel Goemans and David Williamson gave a semidefinite-programming algorithm for maximum cut (Max-Cut: split a graph's vertices into two sides so that as many edges as possible cross) whose solutions have expected value at least 0.87856 times the optimum [1]. Khot stated the conjecture in 2002, together with "d-to-1" conjectures in which each label on one side of a constraint fits exactly d labels on the other [2, 6]. Khot, Guy Kindler, Elchanan Mossel and Ryan O'Donnell then showed that, if the conjecture holds, the Goemans–Williamson algorithm is optimal; their reduction relies on the "Majority Is Stablest" theorem, later proved by Mossel, O'Donnell and Krzysztof Oleszkiewicz [3]. Khot and Oded Regev showed that, under the conjecture, vertex cover cannot be approximated within any constant factor better than 2 [4], the factor that known algorithms achieve [6]. In 2008 Prasad Raghavendra showed that, under the conjecture, for every constraint satisfaction problem a natural semidefinite relaxation gives the best approximation ratio that any efficient algorithm can achieve [5, 6].
Algorithms and small-set expansion (2002–2015). The algorithms Khot surveyed in 2010 fall short of disproving the conjecture: each needs a small label set, an error that shrinks with the instance size, a mildly expanding constraint graph, or more than polynomial time [6]. The algorithm of Arora, Barak and Steurer runs in time exp(k n^ε) on instances with k labels and n variables in which a 1 − ε^c fraction of the constraints can be satisfied, for an absolute constant c, and finds an assignment satisfying a 1 − ε fraction [8]. The authors write that their results "stop short of refuting the UGC" but suggest that Unique Games is significantly easier than problems such as Max 3-SAT [8]. Raghavendra and Steurer reduced the problem of finding a small set of vertices with few edges leaving it to Unique Games, so their small-set expansion hypothesis implies the conjecture [6, 7].
The 2-to-2 theorem (2017–2023). In 2-to-2 games, each label of one variable fits two labels of the other. Khot, Dor Minzer and Muli Safra, building on joint work with Irit Dinur and Kindler and on a contribution from Barak, Pravesh Kothari and Steurer, completed in 2018 the proof of the 2-to-2 games conjecture with imperfect completeness; the journal version appeared in 2023 [9]. It follows that telling unique games of value at least 1/2 − ε from those of value at most ε is NP-hard, and that approximating vertex cover within any factor below √2 is NP-hard, improving the earlier 1.36 [9].
Perfect completeness (2026). An October 2026 preprint by Yumou Fei, Minzer and Shuo Wang, not peer reviewed, proves that 4-to-1 games with perfect completeness are NP-hard, which they write confirms Khot's 4-to-1 games conjecture; one consequence is that colouring a 3-colourable graph with any fixed number of colours is NP-hard [14].
Recent claims. On 6 October 2026 OpenAI released openai/math, a repository of manuscripts "produced by an internal OpenAI model"; one of them, "The Unique Games Theorem" (dated 23 September), claims a deterministic polynomial-time reduction from 3SAT to Unique Games with completeness at least 1 − ε and soundness at most δ for every fixed ε and δ between 0 and 1/2, and companion manuscripts claim direct proofs of the Max-Cut and vertex-cover thresholds [10]. The repository says its results are "at different stages of verification"; this one is listed with a Lean formalisation of that reduction, the review status recorded for the whole formalisation catalogue is "unchecked", and no revision of the manuscript was recorded by 14 October [10]. Scott Aaronson wrote that "no human has understood just about any of these proofs yet", and relayed the view of the complexity theorist Dana Moshkovitz that "The Unique Games Conjecture is true, though it wasn't really needed for the proof of its most famous corollaries", and that "the writeup is poorly written" [11]. Lance Fortnow wrote that "these proofs haven't been fully verified" [12], and Gil Kalai that "even Lean verification may have issues" [13]. On 14 October 2026 the Wikipedia list still included the conjecture [15].
Main approaches
Hardness through codes and local tests. Reduce from a problem already known to be hard, such as satisfiability or linear equations with three variables, by encoding each label with an error-correcting code that can be tested locally; Fourier analysis, or the expansion of the graphs behind the code, shows that the test works [6, 9]. Strongest evidence: the Grassmann-graph analysis behind the 2-to-2 theorem, which gives hardness for Unique Games at completeness 1/2 [9]. Main difficulty: by Arora, Barak and Steurer, the conjecture cannot be proved by a gadget reduction from Label Cover of the kind Johan Håstad pioneered, and a reduction from 3SAT must blow up the instance by a polynomial whose degree grows as ε shrinks [6, 8].
Algorithms that could disprove it. Semidefinite programming, spectral methods and graph decomposition find good labellings in special regimes [6, 8]. Strongest evidence: the subexponential algorithm of Arora, Barak and Steurer, which sets Unique Games apart from problems such as Max 3-SAT [8]. Main difficulty: the known algorithms fall short of disproving the conjecture [6, 8], and Khot, Minzer and Safra argue that, because these attacks work as well at completeness 1/2, where hardness is now proved, they are far from disproving it [9].
Small-set expansion. Prove that finding small, poorly connected sets of vertices is hard; by Raghavendra and Steurer this would imply the conjecture [7]. Strongest evidence: the reduction from small-set expansion to Unique Games [7], and an algorithm for Unique Games obtained by extending one for small-set expansion [8]. Main difficulty: Khot, Minzer and Safra write that the 2-to-2 theorem arguably supports Khot's suspicion that the conjecture may be correct while the small-set expansion hypothesis may be incorrect [9].
Proving the consequences directly. Prove the thresholds that the conjecture gives, 2 for vertex cover and the Goemans–Williamson ratio for Max-Cut, without it [3, 4]. Strongest evidence: the 2-to-2 work proved NP-hardness for vertex cover below √2 and a Max-Cut gap that had been known only under the conjecture [9]. Main difficulty: √2 is still short of 2 [4, 9]; the 2026 manuscripts that claim direct proofs of both thresholds are repository manuscripts, not peer reviewed [10].
Open sub-questions
- Checking the 2026 reduction. Does the soundness analysis of "The Unique Games Theorem" hold as written, and does its Lean statement say the same as the manuscript's main theorem [10]?
- Completeness near 1. Can the Grassmann-graph method, which gives hardness at completeness 1/2 [9], reach completeness 1 − ε, for example through the half-space code that Moshkovitz has raised [11]?
- Running time. What is the exact time complexity of Unique Games at completeness 1 − ε, between the exp(k n^ε) algorithm and the n^(1/ε^0.01) bound on reductions from 3SAT [8]?
- Small-set expansion. Is the small-set expansion hypothesis, which implies the conjecture [7], true, or false as Khot suspects [9]?
- Perfect completeness for 2-to-1 games. Can the 4-to-1 result with perfect completeness [14] be extended to 2-to-1 games, the stricter case [14]? A 2026 manuscript in the openai/math collection claims it [10].
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Goemans, M. X. & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6), 1115–1145. 10.1145/227683.227684 · Checked 14 Oct 2026
- Khot, S. (2002). On the power of unique 2-prover 1-round games. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC '02), 767–775. 10.1145/509907.510017 · Checked 14 Oct 2026
- Khot, S., Kindler, G., Mossel, E. & O'Donnell, R. (2007). Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing 37(1), 319–357. 10.1137/S0097539705447372 · Checked 14 Oct 2026
- Khot, S. & Regev, O. (2008). Vertex cover might be hard to approximate to within 2 − ε. Journal of Computer and System Sciences 74(3), 335–349. 10.1016/j.jcss.2007.06.019 · Checked 14 Oct 2026
- Raghavendra, P. (2008). Optimal algorithms and inapproximability results for every CSP? In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (STOC '08), 245–254. 10.1145/1374376.1374414 · Checked 14 Oct 2026
- Khot, S. (2010). On the unique games conjecture (invited survey). In 2010 IEEE 25th Annual Conference on Computational Complexity (CCC), 99–121. 10.1109/CCC.2010.19 · Checked 14 Oct 2026
- Raghavendra, P. & Steurer, D. (2010). Graph expansion and the unique games conjecture. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC '10), 755–764. 10.1145/1806689.1806792 · Checked 14 Oct 2026
- Arora, S., Barak, B. & Steurer, D. (2015). Subexponential algorithms for unique games and related problems. Journal of the ACM 62(5), 1–25. 10.1145/2775105 · Checked 14 Oct 2026
- Khot, S., Minzer, D. & Safra, M. (2023). Pseudorandom sets in Grassmann graph have near-perfect expansion. Annals of Mathematics 198(1), 1–92. Conference version in FOCS 2018. 10.4007/annals.2023.198.1.1 · Checked 14 Oct 2026
- OpenAI (2026). The Unique Games Theorem. OpenAI Math Release preprint, manuscript dated 23 September 2026, released 6 October 2026, with the other manuscripts of result families 102 and 105. Source · Checked 14 Oct 2026
- Aaronson, S. (2026). The Mathocalypse. Shtetl-Optimized, 7 October 2026 (updated 9 and 12 October), with the author's comment #2 relaying Dana Moshkovitz's remarks. Source · Checked 14 Oct 2026
- Fortnow, L. (2026). Open No More. Computational Complexity blog, 7 October 2026. Source · Checked 14 Oct 2026
- Kalai, G. (2026). Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans. Combinatorics and more, 7 October 2026. Source · Checked 14 Oct 2026
- Fei, Y., Minzer, D. & Wang, S. (2026). On the hardness of 4-to-1 games with perfect completeness. arXiv preprint 2610.12378 (8 October 2026). Source · Checked 14 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 14 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 29 Sep 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.