Unique Games Conjecture: NP-hardness of (1−ε) versus δ satisfiability for unique games at fixed alphabet

Status as of 2026-10-15: open, with an unrefereed AI-generated proof under expert scrutiny.

Conditional results: if UGC holds, the Goemans–Williamson algorithm is optimal for Max-Cut (Khot, Kindler, Mossel, O'Donnell, 2004, together with the Majority Is Stablest theorem of Mossel, O'Donnell and Oleszkiewicz, 2005), Vertex Cover cannot be approximated within $2-\varepsilon$ (Khot and Regev, 2003), and a basic semidefinite program gives the optimal approximation for every constraint satisfaction problem (Raghavendra, 2008). Arora, Barak and Steurer (2010) gave a subexponential-time algorithm for unique games, so the problem is easier than 3-SAT is believed to be, but this does not refute UGC.

Unconditional progress: building on Dinur, Khot, Kindler, Minzer and Safra (2016–17), Khot, Minzer and Safra (ECCC January 2018; Annals of Mathematics 2023) proved the 2-to-2 Games Theorem, which implies that it is NP-hard to distinguish unique games of value at least $1/2$ from those of value at most $\delta$: UGC "with completeness ". On 14 September 2026 Fei, Minzer and Wang (ECCC TR26-179, revised 8 October; not yet refereed) proved the 4-to-1 Games Conjecture with perfect completeness, which with known reductions implies that for every constant it is NP-hard to properly -colour a 3-colourable graph.

Direct applications are limited: UGC is a statement about hardness, so resolving it adds no new algorithm. Its value is in certifying that known algorithms are optimal: that semidefinite-programming-based approximation ratios for Max-Cut and many constraint satisfaction problems, and the factor 2 for Vertex Cover, cannot be improved unless $\mathsf{P}=\mathsf{NP}$. This tells practitioners when to stop searching for better approximation algorithms.

A proof (or refutation) of UGC in the form above, accepted by the complexity-theory community after scrutiny. A machine-checked proof helps only if experts confirm that its formal statement matches the conjecture and that the formal development has no gaps; an unreviewed AI-generated manuscript does not by itself meet this bar.