View source for 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|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|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.

[[Category:Mathematics]]
[[Category:Computer Science]]
[[Category:Complexity]]