The unique games conjecture asserts that for every fixed there is a fixed finite alphabet for which distinguishing unique
games with value at least
from those with value at most
is NP-hard (Trevisan
2012). The alphabet is chosen after the two error parameters.
Unique Games Conjecture
See also
2-to-1 Game, NP-Hard Problem, Unique GameExplore 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