An unproven conjecture in computational complexity theory stating that a particular class of constraint satisfaction problems is hard to approximate even slightly better than a trivial guess, a conjecture that, if true, would settle the optimal approximability of many other well-studied problems at once.
Facts
Connections
Sources
1. Unique games conjecture, Wikipedia
Introduction, sentence beginning 'The unique games conjecture was introduced'Quote, Introduction, sentence beginning 'The unique games conjecture was introduced'
The unique games conjecture was introduced by Subhash Khot in 2002 in order to make progress on certain questions in the theory of hardness of approximation.
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.