TOPICS
Search

Unique Games Conjecture


The unique games conjecture asserts that for every fixed epsilon,delta in (0,1/2) there is a fixed finite alphabet for which distinguishing unique games with value at least 1-epsilon from those with value at most delta is NP-hard (Trevisan 2012). The alphabet is chosen after the two error parameters.


See also

2-to-1 Game, NP-Hard Problem, Unique Game

Explore with Wolfram|Alpha

References

Trevisan, L. "On Khot's Unique Games Conjecture." Bull. Amer. Math. Soc. 49, 91-111, 2012. https://doi.org/10.1090/S0273-0979-2011-01361-1.

Cite this as:

Weisstein, Eric W. "Unique Games Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/UniqueGamesConjecture.html

Subject classifications