Math Conjectures

Unique Games Conjecture

OPENLandmarkConjectureProposed 2002 · Standard version

Canonical statement

For every ε,δ∈(0,1)\varepsilon,\delta\in(0,1), there is an alphabet size qq, where [q]={1,…,q}[q]=\{1,\ldots,q\}, such that the following promise problem is NPNP-hard. The input is a finite directed constraint graph in which every arc u→vu\to v carries a permutation πuv\pi_{uv} of [q][q]; a labeling ℓ:V→[q]\ell:V\to[q] satisfies that arc when ℓ(v)=πuv(ℓ(u))\ell(v)=\pi_{uv}(\ell(u)). Distinguish
YES:some labeling satisfies at least 1−ε of the constraints;NO:every labeling satisfies at most δ of them. \begin{array}{ll} \text{YES:}&\text{some labeling satisfies at least }1-\varepsilon \text{ of the constraints};\\ \text{NO:}&\text{every labeling satisfies at most }\delta \text{ of them.} \end{array}
View source LaTeX
For every \(\varepsilon,\delta\in(0,1)\), there is an
alphabet size \(q\), where \([q]=\{1,\ldots,q\}\), such that the
following promise problem is \(NP\)-hard. The input is a finite directed
constraint graph in which every arc \(u\to v\) carries a permutation
\(\pi_{uv}\) of \([q]\); a labeling \(\ell:V\to[q]\) satisfies that arc
when \(\ell(v)=\pi_{uv}(\ell(u))\). Distinguish
\[
  \begin{array}{ll}
  \text{YES:}&\text{some labeling satisfies at least }1-\varepsilon
  \text{ of the constraints};\\
  \text{NO:}&\text{every labeling satisfies at most }\delta
  \text{ of them.}
  \end{array}
\]
TCS-008:[Khot2002UGC][Raghavendra2008CSP][IAS2026UniqueGames]
Theoretical computer scienceMathematical optimization

Notes

The Unique Games Conjecture, posed by Khot in 2002, concerns constraint graphs in which each edge uvuv carries a permutation πuv\pi_{uv} of a finite alphabet {1,…,q}\{1,\ldots,q\} and a labeling ℓ\ell satisfies the edge if ℓ(v)=πuv(ℓ(u))\ell(v)=\pi_{uv}(\ell(u)). It asserts that for every ε,δ>0\varepsilon,\delta>0 there is an alphabet size qq for which it is NPNP-hard to distinguish instances where some labeling satisfies at least a 1−ε1-\varepsilon fraction of the constraints from instances where every labeling satisfies at most a δ\delta fraction [Khot2002UGC].

Its importance lies in its consequences. Assuming the conjecture, Raghavendra showed that for every constraint-satisfaction problem a canonical semidefinite programming relaxation achieves the optimal approximation ratio, so the conjecture would pin down sharp inapproximability thresholds across a broad landscape of optimization problems [Raghavendra2008CSP]. Strong algorithms and hardness results are known in important parameter regimes, and the conjecture continues to drive intensive research [IAS2026UniqueGames].

Neither the full quantified statement nor its negation has been proved. A resolution requires either an efficient distinguishing algorithm covering all parameter settings or an NPNP-hardness reduction matching the conjectured thresholds.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.