Back Conjetura del Juego Único Spanish Conjecture des jeux uniques French Conjectura de jogos únicos Portuguese
Is the Unique Games Conjecture true?
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]
- ^ a b Klarreich, Erica (October 6, 2011), "Approximately Hard: The Unique Games Conjecture", Simons Foundation, retrieved 2012-10-29
- ^ Lipton, Dick (May 5, 2010), "Unique Games: A Three Act Play", Gödel’s Lost Letter and P=NP, retrieved 2012-10-29
- ^ Cite error: The named reference
khot02onthepowerwas invoked but never defined (see the help page). - ^ The unique games conjecture is vacuously true if P = NP, as then every problem in NP would also be NP-hard.