In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002. It 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. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementThe problem of determining the approximate value of a unique game, a certain type of two-prover game, is NP-hard. 1 Proposed Year Progress Toward ResolutionOpen. In 2018 a weaker version, the 2-2 games conjecture, was proven, which in a certain sense proves half of the original conjecture. In 2010 Arora, Barak and Steurer found a subexponential time approximation algorithm for the unique games problem. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Unique Games Conjecture (Wikipedia)
Sources
1. Unique Games Conjecture (Wikipedia)
Wikimedia FoundationLead section
a conjecture made by Subhash Khot in 2002
Lead section, statement sentence
the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity
Results section, 2018 sentence
In 2018, after a series of papers, a weaker version of the conjecture, called the 2-2 games conjecture, was proven.
Results section, 2010 subexponential algorithm sentence
Boaz Barak and David Steurer found a subexponential time approximation algorithm for the unique games problem.
In Branch: Computational Complexity Theory, Lead sentence
In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.