OP-00733 Solution claimed

The Unique Games Conjecture

A unique game consists of a finite bipartite graph $G = (L \sqcup R, E)$ with $E \ne \varnothing$, an alphabet $[r] = \{1, \dots, r\}$ and, for each edge $e = (u, v)$ directed from $L$ to $R$, a permutation $\pi_e$ of $[r]$. A labeling $\ell : L \sqcup R \to [r]$ satisfies $e$ when $\ell(v) = \pi_e(\ell(u))$, and the value of the game is the largest fraction of edges that a labeling satisfies, $$\operatorname{val}(G, \pi) = \max_{\ell} \frac{1}{|E|} \sum_{e = (u, v) \in E} \mathbf{1}\{\ell(v) = \pi_e(\ell(u))\}.$$ Khot proposed the conjecture below in 2002. Khot, Minzer and Safra completed the proof of the 2-to-2 Games Conjecture with imperfect completeness; as Fei, Minzer and Wang record, it follows that for every $\varepsilon > 0$ there is an $r$ for which it is NP-hard to distinguish unique games of value at least $1/2$ from those of value at most $\varepsilon$. Kempe, Regev and Toner showed that the variant of the conjecture in which the two provers share entanglement is false.

Problem. Is it true that for every $0 < \varepsilon < 1/2$ there is an integer $r = r(\varepsilon)$ such that it is NP-hard to distinguish unique games over $[r]$ with $\operatorname{val}(G, \pi) \ge 1 - \varepsilon$ from those with $\operatorname{val}(G, \pi) \le \varepsilon$? The alphabet is fixed for each $\varepsilon$, independently of the number of vertices; this is a promise problem, with no requirement on instances of intermediate value; and the value is taken over ordinary classical labelings.

Source: Khot (2002), the Unique Games Conjecture; stated by AIM — Open Applied Problems after Fei, Minzer and Wang (2026), Conjecture 1.4.

Imported from github.com/MColbrook/AIM.

Classification

Primary: CO — Combinatorics
Secondary: OC
Keywords: AIM Open Applied Problems, constraint satisfaction, hardness of approximation, Unique Games Conjecture

References

@inproceedings{khot2002,
  author    = {Khot, Subhash},
  title     = {On the power of unique 2-prover 1-round games},
  booktitle = {Proceedings of the Thirty-Fourth Annual {ACM} Symposium on Theory of Computing},
  publisher = {ACM},
  address   = {New York},
  year      = {2002},
  pages     = {767--775},
  doi       = {10.1145/509907.510017},
}
@article{khot2023,
  author  = {Khot, Subhash and Minzer, Dor and Safra, Muli},
  title   = {Pseudorandom sets in {G}rassmann graph have near-perfect expansion},
  journal = {Ann. of Math. (2)},
  volume  = {198},
  number  = {1},
  year    = {2023},
  pages   = {1--92},
  doi     = {10.4007/annals.2023.198.1.1},
}
@techreport{fei2026,
  author      = {Fei, Yumou and Minzer, Dor and Wang, Shuo},
  title       = {On the hardness of 4-to-1 games with perfect completeness},
  institution = {Electronic Colloquium on Computational Complexity},
  type        = {ECCC Report},
  number      = {TR26-179},
  year        = {2026},
  url         = {https://eccc.weizmann.ac.il/report/2026/179/},
}
@article{kempe2010,
  author        = {Kempe, Julia and Regev, Oded and Toner, Ben},
  title         = {Unique games with entangled provers are easy},
  journal       = {SIAM J. Comput.},
  volume        = {39},
  number        = {7},
  year          = {2010},
  pages         = {3207--3229},
  doi           = {10.1137/090772885},
  eprint        = {0710.0655},
  archivePrefix = {arXiv},
}
@misc{aim-unique-games,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{The Unique Games Conjecture}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/1b7c7fd251c1643bb41f0e3cef38704bcef410fd/problems/293-unique-games.md},
  note         = {Entry 293 at commit 1b7c7fd, 2026-10-13},
}

Resolution claims

The Unique Games Theorem v1 GitHub ↗

OpenAI

We prove the Unique Games Conjecture. For every fixed $\varepsilon,\delta\in(0,1/2)$, we give a deterministic polynomial-time reduction from $\mathrm{3SAT}$ to Unique Games over a fixed finite alphabet, with completeness at least $1-\varepsilon$ and soundness at most $\delta$.

Full resolution · not verified · fidelity not established · posted on GitHub 6 Oct 2026

Status history

When	Change	By	Reason
2026-10-16	Needs verification → Solution claimed	—	Recorded here: math @ 1581d4c, build/main.tex.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00733, "The Unique Games Conjecture", clopen.solutions.