← All problems

Unique-Games Conjecture

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
  1. 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
  1. Mark Braverman, Subhash Khot, Noam Lifshitz and Dor Minzer, “An Invariance Principle for the Multi-slice, with Applications”, arXiv:2110.10725 (2025).

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