If the unique games conjecture is true and P ≠ NP,[4] then for many important problems it is not only impossible to get an exact solution in polynomial time (as postulated by the P versus NP problem), but also impossible to get a good polynomial-time approximation.
The conjecture postulates the NP-hardness of the following promise problem known as label cover with unique constraints.
Unique constraints means that for each edge none of the ordered pairs have the same color for the same node.
An assignment to a label cover instance gives to each vertex of G a value in the set [k] = {1, 2, ... k}, often called “colours.” Such instances are strongly constrained in the sense that the colour of a vertex uniquely defines the colours of its neighbours, and hence for its entire connected component.
In particular, the problem of deciding if a given instance admits a satisfying assignment can be solved in polynomial time.
The value of a unique label cover instance is the fraction of constraints that can be satisfied by any assignment.
The unique games conjecture states that for every sufficiently small pair of constants ε, δ > 0, there exists a constant k such that the (1 − δ, ε)-gap label-cover problem with unique constraints over alphabet of size k is NP-hard.
It is not immediately obvious that the inapproximability of Max2Lin(k) is equivalent to the UGC, but this is in fact the case, by a reduction.
It has been argued that the UGC is essentially a question of computational topology,[6] involving local-global principles (the latter are also evident in the proof of the 2-2 Games Conjecture, see below).
Grochow and Tucker-Foltz exhibited a third computational topology problem whose inapproximability is equivalent to the UGC: 1-Cohomology Localization on Triangulations of 2-Manifolds.
The unique games conjecture states that for every sufficiently small pair of constants ε, δ > 0, there exists a constant k such that the following promise problem (Lyes, Lno) is NP-hard: where G is a unique game whose answers come from a set of size k. Alternatively, the unique games conjecture postulates the existence of a certain type of probabilistically checkable proof for problems in NP.
The unique games conjecture states that for every sufficiently small pair of constants
Some very natural, intrinsically interesting statements about things like voting and foams just popped out of studying the UGC....
Even if the UGC turns out to be false, it has inspired a lot of interesting math research.The unique games conjecture was introduced by Subhash Khot in 2002 in order to make progress on certain questions in the theory of hardness of approximation.
The truth of the unique games conjecture would imply the optimality of many known approximation algorithms (assuming P ≠ NP).
means that the result holds for every constant (with respect to the problem size) strictly greater than or less than
If the uniqueness requirement is removed the corresponding statement is known to be true by the parallel repetition theorem, even when
Marek Karpinski and Warren Schudy have constructed linear time approximation schemes for dense instances of unique games problem.
[21] In 2008, Prasad Raghavendra has shown that if the unique games conjecture is true, then for every constraint satisfaction problem the best approximation ratio is given by a certain simple semidefinite programming instance, which is in particular polynomial.
[22] In 2010, Prasad Raghavendra and David Steurer defined the gap-small-set expansion problem, and conjectured that it is NP-hard.
The resulting small set expansion hypothesis implies the unique games conjecture.
[23] It has also been used to prove strong hardness of approximation results for finding complete bipartite subgraphs.
[24] In 2010, Sanjeev Arora, Boaz Barak and David Steurer found a subexponential time approximation algorithm for the unique games problem.