The Unique Games Conjecture

For every ε > 0 there is δ > 0 such that given Unique-Games instances with value ≥ 1 − δ it is NP-hard to find a labelling satisfying ≥ 1 − ε of constraints.

Khot's 2002 conjecture underpinned landmark hardness results (Max-Cut above Goemans–Williamson, vertex-cover constants, ordering problems) via Raghavendra's general theory. Counter-pressure kept arriving: Arora–Barak–Steurer subexponential algorithms (2010), and through the 2020s increasingly strong constant-factor and 2-to-1-games results (Khot–Minzer–Safra's 2-to-1 proof being the structural high-water mark) squeezed the space of plausible hard instances. Whether UGC is literally true now looks genuinely uncertain — the directory records it as the field's most consequential open bet.