MathDB

Unique-Games Conjecture

About 5 years old · traced to

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 ε,s>0\varepsilon,s>0, let nn be the alphabet size. Unique-Games Conjecture. For all ε,s>0\varepsilon,s>0, there is n∈Nn\in\mathbb{N} such that, given a Unique-Games instance Ψ\Psi with alphabet size nn, it is NP-hard to distinguish between the following cases: there is an assignment to Ψ\Psi satisfying at least 1−ε1-\varepsilon fraction of the constraints, and there is no assignment to Ψ\Psi satisfying more than an ss 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.

  1. 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 ε>0\varepsilon>0, distinguishing whether the instance has value at least 1−ε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 αGW\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).

complexity-theoryconstraint-satisfactionhardness-of-approximationunique-games
Posted · edited

Progress summary

Refreshed
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 22-to-22 Games Conjecture, giving hardness near 50%50\% completeness, not the required regime near 100%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 22-to-22 result does not resolve the original conjecture.

Sources

Solutions 1

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
0
Shaowu Zhang Posted · edited