Unique games conjecture

Unsolved problem in computer science:
Is the Unique Games Conjecture true?
(more unsolved problems in computer science)

In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002.[1][2][3] The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP,[4] then for many important problems it is not only impossible to get an exact solution in polynomial time (as postulated by the P versus NP problem), but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.

The conjecture is unusual in that the academic world seems about evenly divided on whether it is true or not.[1]

  1. ^ a b Klarreich, Erica (October 6, 2011), "Approximately Hard: The Unique Games Conjecture", Simons Foundation, retrieved 2012-10-29
  2. ^ Lipton, Dick (May 5, 2010), "Unique Games: A Three Act Play", Gödel’s Lost Letter and P=NP, retrieved 2012-10-29
  3. ^ Cite error: The named reference khot02onthepower was invoked but never defined (see the help page).
  4. ^ The unique games conjecture is vacuously true if P = NP, as then every problem in NP would also be NP-hard.