The unique games conjecture
In a unique game, variables take labels from a set of size , and each constraint on a pair of variables says that the label of is a fixed permutation of the label of . Prove or refute that for every there is a such that it is NP-hard to distinguish instances where at least a fraction of the constraints can be satisfied from instances where at most an fraction can.
History and references
Still open as of 2026.
Subhash Khot proposed the conjecture in 2002. If it is true, many simple approximation algorithms are the best possible unless P = NP. For example, the Goemans–Williamson algorithm would be optimal for Max-Cut, and minimum vertex cover could not be approximated within a factor in polynomial time. In 2018 Khot, Minzer and Safra proved the related 2-to-2 games conjecture, which is sometimes described as proving half of the unique games conjecture. Experts remain roughly evenly divided on whether the full conjecture is true.
References
Solutions 0
Sign in or create an account to publish a solution