Computer science Randomized, circuit, counting and interactive complexity Conjecture

Unique games conjecture

Statement

A unique game with alphabet size $k$ is given by a finite graph $G = (V, E)$ and, for each edge $e = \set{u, v}$ , a permutation $\pi_e$ of $\set{1, \ldots, k}$ . A labeling $\ell \colon V \to \set{1, \ldots, k}$ satisfies the edge $e$ if $\pi_e(\ell(u)) = \ell(v)$ , with the edge read in a fixed direction. The value of the game is the largest fraction of edges satisfied by a labeling.

Conjecture. For every $\varepsilon > 0$ and $\delta > 0$ there is an integer $k$ with the following property. Consider unique games with alphabet size $k$ . It is NP-hard to distinguish those of value at least $1 - \varepsilon$ from those of value at most $\delta$ .

Remarks

The conjecture is open. Deciding whether the value is exactly $1$ is easy: fixing the label of one vertex in each connected component forces all other labels. So the conjecture concerns only nearly satisfiable games.

If the conjecture holds, several known approximation algorithms are optimal. Khot, Kindler, Mossel and O'Donnell showed that the Goemans–Williamson ratio for MAX-CUT, about $0.878$ , cannot then be beaten in polynomial time unless $\mathrm{P} = \mathrm{NP}$ . Khot and Regev showed that vertex cover would then be NP-hard to approximate within $2 - \varepsilon$ for every $\varepsilon > 0$ .

In 2018 Khot, Minzer and Safra, building on joint work with Dinur and Kindler, proved the 2-to-2 games conjecture. A consequence is the weaker form of the conjecture with completeness $1/2$ in place of $1 - \varepsilon$ .

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Graph concept
NP-hardness concept
Unique games conjecture conjecture

Where this leads

1 page builds on this one.

Goemans–Williamson algorithm

Tag	`SWZ51W5WJ4`
URI	`m2://SWZ51W5WJ4`
Kind	conjecture
Writing	W0 stub
MSC	68Q17, 68Q25
Status	This copy of the site has no build data. Run `m2 status SWZ51W5WJ4`.
About	Hardness of approximation
Uses	NP-hardness, Graph
Changed	3 November 2026

Unique games conjecture

Statement

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by