= Unique games conjecture
{wiki=Unique_games_conjecture}
The Unique Games Conjecture (UGC) is a hypothesis in the field of computational complexity theory, proposed by Subhash Khot in 2002. It addresses the approximability of certain optimization problems. Specifically, the conjecture asserts that for a certain class of problems, particularly those related to constraint satisfaction, there exist strong connections between the complexity of finding solutions and the difficulty of distinguishing between close and far solutions.
Back to article page