Formulations
The unique games conjecture can be stated in a number of equivalent ways.Unique label cover
The following formulation of the unique games conjecture is often used in hardness of approximation. The conjecture postulates the NP-hardness of the following promise problem known as ''label cover with unique constraints''. For each edge, the colors on the two vertices are restricted to some particular ordered pairs. ''Unique'' constraints means that for each edge none of the ordered pairs have the same color for the same node. This means that an instance of label cover with unique constraints over an alphabet of size ''k'' can be represented as a directed graph together with a collection ofMaximizing Linear Equations Modulo k
Consider the following system of linear equations over the integers modulo k: : When each equation involves exactly two variables, this is an instance of the label cover problem with unique constraints; such instances are known as instances of the Max2Lin(k) problem. 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. Namely, the UGC is equivalent to: for every sufficiently small pair of constants ''ε'', ''δ'' > 0, there exists a constant ''k'' such that the (1 − ''δ'', ''ε'')-gap Max2Lin(k) problem is NP-hard.Connection with computational topology
It has been argued that the UGC is essentially a question of computational topology, involving local-global principles (the latter are also evident in the proof of the 2-2 Games Conjecture, see below). Linial observed that unique label cover is an instance of the Maximum Section of a Covering Graph problem (covering graphs is the terminology fromTwo-prover proof systems
A unique game is a special case of a ''two-prover one-round (2P1R) game''. A two-prover one-round game has two players (also known as provers) and a referee. The referee sends each player a question drawn from a knownProbabilistically checkable proofs
Alternatively, the unique games conjecture postulates the existence of a certain type of probabilistically checkable proof for problems in NP. A unique game can be viewed as a special kind of nonadaptive probabilistically checkable proof with query complexity 2, where for each pair of possible queries of the verifier and each possible answer to the first query, there is exactly one possible answer to the second query that makes the verifier accept, and vice versa. The unique games conjecture states that for every sufficiently small pair of constants there is a constant such that every problem in NP has a probabilistically checkable proof over an alphabet of size with completeness , soundness , and randomness complexity which is a unique game.Relevance
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). For example, the approximation ratio achieved by the algorithm of Goemans and Williamson for approximating the maximum cut in a graph is optimal to within any additive constant assuming the unique games conjecture and P ≠ NP. A list of results that the unique games conjecture is known to imply is shown in the adjacent table together with the corresponding best results for the weaker assumption P ≠ NP. A constant of or means that the result holds for every ''constant'' (with respect to the problem size) strictly greater than or less than , respectively.Discussion and alternatives
Currently, there is no consensus regarding the truth of the unique games conjecture. Certain stronger forms of the conjecture have been disproved. A different form of the conjecture postulates that distinguishing the case when the value of a unique game is at least from the case when the value is at most is impossible for polynomial-time algorithms (but perhaps not NP-hard). This form of the conjecture would still be useful for applications in hardness of approximation. The constant in the above formulations of the conjecture is necessary unless P = NP. If the uniqueness requirement is removed the corresponding statement is known to be true by the parallel repetition theorem, evenResults
Marek Karpinski and Warren Schudy have constructed linear time approximation schemes for dense instances of unique games problem. 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. 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. It has also been used to prove strong hardness of approximation results for finding complete bipartite subgraphs. In 2010, Sanjeev Arora, Boaz Barak and David Steurer found a subexponential time approximation algorithm for the unique games problem. A key ingredient in their result was the spectral algorithm of Alexandra Kolla (see also the earlier manuscript of A. Kolla and Madhur Tulsiani). The latter also re-proved that unique games on expander graphs could be solved in polynomial time, and was one of (if not the) first graph algorithms to take advantage of the full spectrum of a graph rather than just its first two eigenvalues. In 2012, it was shown that distinguishing instances with value at most from instances with value at least is NP-hard. In 2018, after a series of papers, a weaker version of the conjecture, called the 2-2 games conjecture, was proven. In a certain sense, this proves "a half" of the original conjecture. This also improves the best known gap for unique label cover: it is NP-hard to distinguish instances with value at most from instances with value at least .References
Further reading
* . {{Computational hardness assumptions 2002 in computing Approximation algorithms Computational complexity theory Computational hardness assumptions Unsolved problems in computer science Conjectures