Source: wikibot/unique-games-conjecture

= 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.