Unique Games Conjecture: A Surprisingly Divisive Problem in Computational Complexity

Proposed by Subhash Khot in 2002, the Unique Games Conjecture (UGC) posits that approximating the value of a specific type of game, known as a unique game, is NP-hard. This conjecture has significant implications for the theory of approximation algorithms; if true and P≠NP, many crucial problems wouldn't allow for good polynomial-time approximations, not just exact solutions. The academic community is split on its validity, with equivalent formulations including label cover and Max2Lin(k) problems. While stronger versions have been disproven, the UGC's exploration has spurred substantial mathematical research, and some progress towards proving it has been made, including proving a related conjecture, the 2-2 games conjecture.