Unique-Games Conjecture

About 5 years old · traced to 2021

A Unique-Games instance is a 1-to-1 Games instance: a 2-Prover-1-Round Games instance in which the two alphabets have equal size and every constraint is a bijection between them. For $\varepsilon,s>0$ , let $n$ be the alphabet size. Unique-Games Conjecture. For all $\varepsilon,s>0$ , there is $n\in\mathbb{N}$ such that, given a Unique-Games instance $\Psi$ with alphabet size $n$ , it is NP-hard to distinguish between the following cases: there is an assignment to $\Psi$ satisfying at least $1-\varepsilon$ fraction of the constraints, and there is no assignment to $\Psi$ satisfying more than an $s$ fraction of the constraints. The conjecture is presented as the standard imperfect-completeness hardness assumption for Unique Games. The supplied status evidence does not resolve this conjecture.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

The Unique Games Conjecture
Let an instance of the Unique Games Problem consist of a graph, a set of colors, and a matching of the colors for each edge. The value of an instance is the largest fraction of edge constraints that can be satisfied by a coloring. Unique Games Conjecture. For every $\varepsilon>0$ , distinguishing whether the instance has value at least $1-\varepsilon$ or value at most $\varepsilon$ is NP-hard. This conjecture is central to hardness-of-approximation results; in particular, the source states that achieving an approximation ratio for Max-Cut better than $\alpha_{GW}$ is UG-hard, so the conjecture is not being presented as an unresolved claim here.
source: Afonso S. Bandeira, Amit Singer and Thomas Strohmer, “Mathematics of Data Science”, arXiv:2607.11938 (2026).

References

Primary source

Mark Braverman, Subhash Khot, Noam Lifshitz and Dor Minzer, “An Invariance Principle for the Multi-slice, with Applications”, arXiv:2110.10725 (2025).

Posted 1 month ago · edited 17 hours ago

Progress summary

Refreshed 17 hours ago

Open

The conjecture remains open, while a 2026 claim that OpenAI proved it has received no independent mathematical verification.

Subhash Khot proposed the Unique-Games Conjecture in 2002. It asks whether distinguishing instances satisfying almost all constraints from those satisfying only a tiny fraction is NP-hard.

Known results

Raghavendra (2008): the conjecture would imply optimal semidefinite-programming approximation algorithms for broad constraint-satisfaction problems.
Khot–Minzer–Safra and collaborators (2018): proved the related $2$ -to- $2$ Games Conjecture, giving hardness near $50\%$ completeness, not the required regime near $100\%$ .

October 7, 2026 community submission (unverified)

A submitted note attributes a purported proof to OpenAI and points to a September 23, 2026 manuscript, but the supplied scans found no independent assessment or verification of its mathematics.

Current status (as of October 2026): The Unique-Games Conjecture remains unsettled; the OpenAI attribution is an unverified submission, and the established $2$ -to- $2$ result does not resolve the original conjecture.

Sources

Claimed by OpenAI: the Unique Games Conjecture.See full solutionHide full solution

Claimed by OpenAI.

Attached: OpenAI, The Unique Games Theorem (September 23, 2026).

GitHub repository: https://github.com/openai/math

Original PDF: https://github.com/openai/math/blob/main/preprints/The-Unique-Games-Theorem-September-23-2026/paper.pdf

This post attributes the claim to OpenAI; it does not independently verify the proof.

102.pdf801,214 bytesOpen

The Unique Games Conjecture

Primary source

Progress summary