Unique games conjecture

Rare card · No. 18692

In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002, that it is NP-hard to approximate the value of a certain type of game, known as a unique game. It has broad applications in the theory of hardness of approximation. If the UGC is true and P ≠ NP, then for many important problems there not only does not exist an algorithm that always produces an exact solution in polynomial time (as postulated by the P versus NP problem), but even an algorithm that always produces a good approximation in polynomial time. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines. According to Ryan O'Donnell as quoted by the Simons Foundation in 2012, academics were roughly evenly divided on whether the conjecture is true or false. In 2026, the OpenAI bulk release of mathematical papers included a paper that claimed to have...

Read on Wikipedia