Software:Unique games conjecture
Unsolved problem in computer science: Is the Unique Games Conjecture true? (more unsolved problems in computer science)

In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002.^{[1]}^{[2]}^{[3]} The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NPhard computational complexity. It has broad applications in the theory of hardness of approximation. 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 polynomialtime approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.
The conjecture is unusual in that the academic world seems about evenly divided on whether it is true or not.^{[1]}
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 NPhardness 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 of permutations π_{e}: [k] → [k], one for each edge e of the graph. 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. Thus, if the input instance admits a valid assignment, then such an assignment can be found efficiently by iterating over all colours of a single node. 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. For satisfiable instances, this value is 1 and is easy to find. On the other hand, it seems to be very difficult to determine the value of an unsatisfiable game, even approximately. The unique games conjecture formalises this difficulty.
More formally, the (c, s)gap labelcover problem with unique constraints is the following promise problem (L_{yes}, L_{no}):
 L_{yes} = {G: Some assignment satisfies at least a cfraction of constraints in G}
 L_{no} = {G: Every assignment satisfies at most an sfraction of constraints in G}
where G is an instance of the label cover problem with unique constraints.
The unique games conjecture states that for every sufficiently small pair of constants ε, δ > 0, there exists a constant k such that the (1 − δ, ε)gap labelcover problem with unique constraints over alphabet of size k is NPhard.
Instead of graphs, the label cover problem can be formulated in terms of linear equations. For example, suppose that we have a system of linear equations over the integers modulo 7:
 [math]\displaystyle{ \begin{align} x_1 & \equiv 2\cdot x_2 \pmod 7, \\ x_2 & \equiv 4\cdot x_5 \pmod 7, \\ & {}\ \ \vdots \\ x_1 & \equiv 2\cdot x_7 \pmod 7. \end{align} }[/math]
This is an instance of the label cover problem with unique constraints. For example, the first equation corresponds to the permutation π_{(1, 2)} where π_{(1, 2)}(x_{1}) = 2x_{2} modulo 7.
Twoprover proof systems
A unique game is a special case of a twoprover oneround (2P1R) game. A twoprover oneround game has two players (also known as provers) and a referee. The referee sends each player a question drawn from a known probability distribution, and the players each have to send an answer. The answers come from a set of fixed size. The game is specified by a predicate that depends on the questions sent to the players and the answers provided by them.
The players may decide on a strategy beforehand, although they cannot communicate with each other during the game. The players win if the predicate is satisfied by their questions and their answers.
A twoprover oneround game is called a unique game if for every question and every answer by the first player, there is exactly one answer by the second player that results in a win for the players, and vice versa. The value of a game is the maximum winning probability for the players over all strategies.
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 (L_{yes}, L_{no}) is NPhard:
 L_{yes} = {G: the value of G is at least 1 − δ}
 L_{no} = {G: the value of G is at most ε}
where G is a unique game whose answers come from a set of size k.
Probabilistically 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 [math]\displaystyle{ \varepsilon,\delta\gt 0 }[/math] there is a constant [math]\displaystyle{ K }[/math] such that every problem in NP has a probabilistically checkable proof over an alphabet of size [math]\displaystyle{ K }[/math] with completeness [math]\displaystyle{ 1\delta }[/math], soundness [math]\displaystyle{ \varepsilon }[/math], and randomness complexity [math]\displaystyle{ O(\log n) }[/math] which is a unique game.
Relevance
Problem  Poly.time approx.  NP hardness  UG hardness 

Max cut  [math]\displaystyle{ 0.878...\dots }[/math]^{[5]}  [math]\displaystyle{ \tfrac{16}{17}+\varepsilon\approx 0.941 }[/math]^{[6]}  [math]\displaystyle{ 0.878\dots+\varepsilon }[/math]^{[7]} 
Min vertex cover  [math]\displaystyle{ 2 }[/math]  [math]\displaystyle{ \sqrt 2\varepsilon }[/math]^{[8]}  [math]\displaystyle{ 2\varepsilon }[/math]^{[9]} 
Feedback arc set  [math]\displaystyle{ O(\log n\log\log n) }[/math]^{[10]}  [math]\displaystyle{ 1.360\dots\varepsilon }[/math]^{[11]}  All constants^{[12]} 
Max acyclic subgraph  [math]\displaystyle{ \tfrac12+\Omega(1/\sqrt\Delta) }[/math]^{[13]}  [math]\displaystyle{ \tfrac{65}{66} }[/math]^{[14]}  [math]\displaystyle{ \tfrac12+\varepsilon }[/math]^{[12]} 
Betweenness  [math]\displaystyle{ \tfrac13 }[/math]  [math]\displaystyle{ \tfrac{47}{48} }[/math]^{[15]}  [math]\displaystyle{ \tfrac13+\varepsilon }[/math]^{[16]} 
“  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.  ” 
— Ryan O’Donnell, ^{[1]} 
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 [math]\displaystyle{ c+\varepsilon }[/math] or [math]\displaystyle{ c\varepsilon }[/math] means that the result holds for every constant (with respect to the problem size) strictly greater than or less than [math]\displaystyle{ c }[/math], 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 [math]\displaystyle{ 1\delta }[/math] from the case when the value is at most [math]\displaystyle{ \varepsilon }[/math] is impossible for polynomialtime algorithms (but perhaps not NPhard). This form of the conjecture would still be useful for applications in hardness of approximation.
The constant [math]\displaystyle{ \delta\gt 0 }[/math] 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, even when [math]\displaystyle{ \delta=0 }[/math].
Marek Karpinski and Warren Schudy have constructed linear time approximation schemes for dense instances of unique games problem.^{[17]}
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.^{[18]}
In 2010, Prasad Raghavendra and David Steurer defined the GapSmallSet Expansion problem, and conjectured that it is NPhard. This conjecture implies the unique games conjecture.^{[19]} It has also been used to prove strong hardness of approximation results for finding complete bipartite subgraphs.^{[20]}
In 2010, Sanjeev Arora, Boaz Barak and David Steurer found a subexponential time approximation algorithm for the unique games problem.^{[21]}
In 2012, it was shown that distinguishing instances with value at most [math]\displaystyle{ \tfrac38+\delta }[/math] from instances with value at least [math]\displaystyle{ \tfrac12 }[/math] is NPhard.^{[22]}
In 2018, after a series of papers, a weaker version of the conjecture, called the 22 games conjecture, was proven. In a certain sense, this proves "a half" of the original conjecture.^{[23]}^{[24]} This also improves the best known gap for unique label cover: it is NPhard to distinguish instances with value at most [math]\displaystyle{ \delta }[/math] from instances with value at least [math]\displaystyle{ \tfrac12 }[/math].^{[25]}
Notes
 ↑ ^{1.0} ^{1.1} ^{1.2} "Approximately Hard: The Unique Games Conjecture", Simons Foundation, 20111006, http://simonsfoundation.org/features/featurearticles/mathematicsandphysicalscience/approximatelyhardtheuniquegamesconjecture/, retrieved 20121029
 ↑ "Unique Games: A Three Act Play", Gödel’s Lost Letter and P=NP, 20100505, http://rjlipton.wordpress.com/2010/05/05/uniquegamesathreeactplay/, retrieved 20121029
 ↑ Khot, Subhash (2002), "On the power of unique 2prover 1round games", Proceedings of the thirtyfourth annual ACM symposium on Theory of computing, pp. 767–775, doi:10.1145/509907.510017, ISBN 1581134959
 ↑ The unique games conjecture is vacuously true if P = NP, as then every problem in NP would also be NPhard.
 ↑ "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming", Journal of the ACM 42 (6): 1115–1145, 1995, doi:10.1145/227683.227684
 ↑ Håstad, Johan (1999), "Some Optimal Inapproximability Results", Journal of the ACM 48 (4): 798–859, doi:10.1145/502090.502098, http://www.nada.kth.se/~johanh/optimalinap.ps.
 ↑ Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "Optimal inapproximability results for MAXCUT and other twovariable CSPs?", SIAM Journal on Computing 37 (1): 319–357, doi:10.1137/S0097539705447372, http://www.cs.cornell.edu/~abrahao/tdg/papers/KKMOmaxcut.pdf
 ↑ "Pseudorandom Sets in Grassmann Graph Have NearPerfect Expansion", 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 2018, pp. 592–601, doi:10.1109/FOCS.2018.00062, ISBN 9781538642306, https://ieeexplore.ieee.org/document/8555140
 ↑ Khot, Subhash; Regev, Oded (2003), "Vertex cover might be hard to approximate to within 2 − ε", IEEE Conference on Computational Complexity: 379–
 ↑ Even, G. (1998), "Approximating minimum feedback sets and multicuts in directed graphs", Algorithmica 20 (2): 151–174, doi:10.1007/PL00009191
 ↑ "On the hardness of approximating minimum vertex cover", Annals of Mathematics 162 (1): 439–485, 2005, doi:10.4007/annals.2005.162.439, http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/vc.pdf, retrieved 20100305.
 ↑ ^{12.0} ^{12.1} Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad (2008), "Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph", 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 2528, 2008, Philadelphia, PA, USA, pp. 573–582, doi:10.1109/FOCS.2008.51
 ↑ "Tight bounds for the maximum acyclic subgraph problem", Journal of Algorithms 25 (1): 1–18, 1997, doi:10.1006/jagm.1997.0864
 ↑ Newman, A. (June 2000), Approximating the maximum acyclic subgraph, Massachusetts Institute of Technology, as cited by (Guruswami Manokaran)
 ↑ "A geometric approach to betweenness", SIAM Journal on Discrete Mathematics 11 (4): 511–523 (electronic), 1998, doi:10.1137/S0895480195296221.
 ↑ "Every permutation CSP of arity 3 is approximation resistant", 24th Annual IEEE Conference on Computational Complexity, 2009, pp. 62–73, doi:10.1109/CCC.2009.29.
 ↑ Karpinski, Marek; Schudy, Warren (2009), "Linear time approximation schemes for the GaleBerlekamp game and related minimization problems", Proceedings of the fortyfirst annual ACM symposium on Theory of computing, pp. 313–322, doi:10.1145/1536414.1536458, ISBN 9781605585062
 ↑ Raghavendra, Prasad (2008), "Optimal algorithms and inapproximability results for every CSP?", Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 1720, 2008, Association for Computing Machinery, pp. 245–254, doi:10.1145/1374376.1374414, https://people.eecs.berkeley.edu/~prasad/Files/extabstract.pdf
 ↑ Raghavendra, Prasad; Steurer, David (2010), "Graph expansion and the unique games conjecture", STOC'10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, Association for Computing Machinery, pp. 755–764, doi:10.1145/1806689.1806792, https://people.eecs.berkeley.edu/~prasad/Files/expansion.pdf
 ↑ Manurangsi, Pasin (2017), "Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum kCut from the Small Set Expansion Hypothesis", in Chatzigiannakis, Ioannis, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Leibniz International Proceedings in Informatics (LIPIcs), 80, Dagstuhl, Germany: Schloss Dagstuhl–LeibnizZentrum fuer Informatik, pp. 79:1–79:14, doi:10.4230/LIPIcs.ICALP.2017.79, ISBN 9783959770415
 ↑ "Subexponential algorithms for unique games and related problems", Journal of the ACM 62 (5): Art. 42, 25, 2015, doi:10.1145/2775105. Previously announced at FOCS 2010.
 ↑ O'Donnell, Ryan; Wright, John (2012), "A new point of NPhardness for unique games", Proceedings of the 2012 ACM Symposium on Theory of Computing (STOC'12), New York: ACM, pp. 289–306, doi:10.1145/2213977.2214005.
 ↑ Klarreich, Erica (April 24, 2018), "First Big Steps Toward Proving the Unique Games Conjecture", Quanta Magazine, https://www.quantamagazine.org/computerscientistscloseinonuniquegamesconjectureproof20180424/
 ↑ Barak, Boaz (20180110) (in en), Unique Games Conjecture – halfway there?, https://windowsontheory.org/2018/01/10/uniquegamesconjecturehalfwaythere/, retrieved 20230315
 ↑ Khot, Subhash; Minzer, Dor; Safra, M. (October 2018), "Pseudorandom Sets in Grassmann Graph Have NearPerfect Expansion", 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 592–601, doi:10.1109/FOCS.2018.00062, ISBN 9781538642306, https://ieeexplore.ieee.org/document/8555140
<ref>
tag with name "FG95approximating" defined in <references>
is not used in prior text.References
 Khot, Subhash (2010), "On the Unique Games Conjecture", Proc. 25th IEEE Conference on Computational Complexity, pp. 99–121, doi:10.1109/CCC.2010.19, http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf.