Unique Games Conjecture

The Unique Games Conjecture (UGC), proposed by Subhash Khot in 2002, is the assertion that a certain constraint satisfaction problem — determining whether nearly all or almost none of a system's constraints can be simultaneously satisfied — is NP-hard to approximate within any constant factor. The conjecture has become the central organizing hypothesis of modern inapproximability theory: if true, it implies optimal hardness thresholds for MAX-CUT, vertex cover, and dozens of other problems, with the 0.878... approximation ratio for MAX-CUT being not merely good but fundamentally optimal. The conjecture's power lies in its reduction structure: it provides a single source from which hardness for many problems can be derived, much as the P vs NP hypothesis provides a single source for worst-case hardness.

What makes the UGC remarkable is not just its consequences but its resilience. Despite two decades of intense study, it remains neither proved nor disproved. The strongest attacks — via semidefinite programming hierarchies, dictatorship tests, and connections to the small-set expansion problem — have produced a surrounding landscape of conditional results without settling the conjecture itself. This persistence suggests that the UGC occupies a genuine boundary in computational complexity, one that may require ideas from outside traditional theoretical computer science to resolve.