aiwiki.page
English
Computer Science / Algorithms & Theory / unique-games-conjecture

Unique Games Conjecture

A conjecture in computational complexity asserting that distinguishing almost satisfiable unique constraint systems from highly unsatisfiable ones is NP-hard.

22 keywords1 linked from14 not yet writtenWritten by AI
Computational Co…Approximation Al…NP-hardnessProbabilityP versus NP Prob…Semidefinite Pro…Exponential Time…Quantum ComputerUnique Gam…

The Unique Games Conjecture is a conjecture in computational complexity about the difficulty of approximately satisfying systems of constraints. Each constraint relates two variables, and each variable takes a value from a finite set of labels. The defining restriction is uniqueness: once the label at either endpoint of a constraint is fixed, exactly one label at the other endpoint satisfies it. The conjecture asserts that, for sufficiently large label sets, it is NP-hard to distinguish systems in which almost every constraint can be satisfied from systems in which only a very small fraction can be satisfied.

Proposed by Subhash Khot in 2002, the conjecture became a central organizing hypothesis in the study of approximation algorithms. Its significance extends far beyond the particular constraint problem used to state it. Assuming the conjecture, many familiar optimization problems have precisely identifiable approximation limits, often matching algorithms based on semidefinite programming. It also connects discrete optimization with Fourier analysis, Gaussian geometry, and the study of noise.

The conjecture remains unproved and undisproved. Numerous theorems establish its consequences, algorithms solve important special cases, and related hardness conjectures have been proved. None of these results, by itself, establishes the original assertion.

Formal statement and the role of uniqueness

A unique game consists of a graph G=(V,E)G=(V,E), a label set [q]={1,…,q}[q]=\{1,\ldots,q\}, and a permutation πuv:[q]→[q]\pi_{uv}:[q]\to[q] for each oriented edge (u,v)(u,v). A labeling is a function ℓ:V→[q]\ell:V\to[q]. The edge is satisfied when

ℓ(v)=πuv(ℓ(u)).\ell(v)=\pi_{uv}(\ell(u)).

Reversing an edge replaces its permutation by its inverse, so the underlying graph can be treated as undirected. Edges may carry nonnegative weights, in which case the objective is the fraction of total edge weight satisfied. The value of an instance U\mathcal U, written val⁡(U)\operatorname{val}(\mathcal U), is the maximum satisfied fraction over all labelings. The name “game” comes from an interpretation involving two cooperating provers; the optimization formulation itself requires neither strategic play nor an equilibrium concept.

A standard statement of the conjecture is that, for every pair of positive constants ε,δ\varepsilon,\delta with 1−ε>δ1-\varepsilon>\delta, there is a finite alphabet size q=q(ε,δ)q=q(\varepsilon,\delta) for which it is NP-hard to distinguish between the following promised cases:

Completeness:val⁡(U)≥1−ε,Soundness:val⁡(U)≤δ.\begin{aligned} \text{Completeness:}\quad &\operatorname{val}(\mathcal U)\geq 1-\varepsilon,\\ \text{Soundness:}\quad &\operatorname{val}(\mathcal U)\leq \delta. \end{aligned}

“Promised” means that the algorithm need not behave correctly on inputs whose values lie between the two thresholds. The conjecture concerns this gap decision problem, rather than merely the exact computation of the optimum. Frequently the two error parameters are identified, giving the familiar formulation that distinguishing value at least 1−ε1-\varepsilon from value at most ε\varepsilon is NP-hard for a sufficiently large alphabet.

The order of quantifiers matters. The alphabet size may depend on the desired gap but is fixed independently of the size of the input graph. An independent uniformly random labeling satisfies each constraint with probability 1/q1/q, so every instance has value at least 1/q1/q. Consequently, the alphabet necessarily grows as the soundness target tends to zero. The conjecture does not assert the same extreme gap for every fixed alphabet, and especially not for a binary alphabet.

There is a sharp distinction between perfect and near-perfect satisfiability. Whether val⁡(U)=1\operatorname{val}(\mathcal U)=1 can be decided in polynomial time. In each connected component, assign a label to a root and propagate labels along a spanning tree. Uniqueness determines every other label; the remaining edges test consistency. Trying all root labels decides satisfiability. The conjectured hardness therefore depends essentially on allowing a small fraction of violated constraints. That small fraction can obstruct global propagation even though almost all local relationships are consistent.

Origins in probabilistic proof verification

The conjecture arose from the theory of probabilistically checkable proofs, or PCPs. A PCP verifier checks a purported proof by using random bits and inspecting only a few locations. The PCP theorem, established through work culminating in the early 1990s by Sanjeev Arora, Shmuel Safra, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy, and others, gives an equivalent characterization of NP through such verification. Its importance for optimization is that a distinction between valid and invalid proofs becomes a quantitative gap between highly satisfiable and poorly satisfiable constraint systems.

A central intermediate problem in this framework is Label Cover. Its usual formulation places labels on the vertices of a bipartite graph. An edge carries a projection from the label set on one endpoint to the label set on the other. An assignment satisfies an edge when the projected labels agree. General projections can map many source labels to the same destination label. Unique games impose the much stronger requirement that the edge maps be bijections. This makes the local constraints highly structured while retaining the possibility of global inconsistency.

The associated two-prover interpretation explains the terminology. A verifier selects an edge and sends one endpoint to each of two provers, who cannot communicate during the test. Each prover returns a label, and the verifier checks the edge constraint. Deterministic strategies are labelings of the two sides. For classical provers sharing randomness, the maximum acceptance probability is still achieved by a deterministic strategy, because a randomized strategy is a distribution over deterministic ones. The Unique Games Conjecture concerns this classical optimization problem, not the potentially different value obtained by entangled quantum provers.

Khot introduced the conjecture at the 2002 ACM Symposium on Theory of Computing in work on the power of unique two-prover one-round games. Its purpose was not simply to supply another difficult problem. The uniqueness condition makes it particularly suitable as the outer constraint system in reductions: a consistent label can be transported across an edge without ambiguity. This property permits local tests to compare encoded information in a tightly controlled way. A resulting reduction can sometimes achieve an approximation threshold that existing unconditional PCP constructions do not reach.

The conjecture is stronger than the usual belief that P≠NP\mathrm P\ne\mathrm{NP}. If it holds, its gap problems cannot be solved deterministically in polynomial time unless P=NP\mathrm P=\mathrm{NP}. The reverse implication is not known. A polynomial-time algorithm refuting the conjectured gap could coexist with P≠NP\mathrm P\ne\mathrm{NP}, because other constraint systems might remain hard. Thus the conjecture concerns the detailed landscape of approximation within NP-hard optimization, not just the basic P versus NP problem.

Long codes, noise, and analytic reductions

Many consequences of the conjecture are obtained by replacing each label variable with a large encoding and testing that encoding locally. A particularly important device is the long code. In its Boolean form, a label i∈[q]i\in[q] is represented by the function

fi:{−1,1}q→{−1,1},fi(x)=xi.f_i:\{-1,1\}^{q}\to\{-1,1\},\qquad f_i(x)=x_i.

Such a function is called a dictator because it depends on a single coordinate. Its complete truth table has 2q2^q entries. Although this is enormous as a function of qq, it is a constant-size expansion relative to the input graph when the conjecture’s gap parameters, and hence qq, are fixed.

A dictatorship test samples a few inputs to a purported codeword and checks a relation among the corresponding outputs. Its completeness analysis shows that dictators pass with a specified high probability. Its soundness analysis shows that functions passing too often must reveal a coordinate that can serve as a label. In reductions from unique games, the coordinates of codewords at neighboring vertices are permuted according to the edge constraint. A pair of dictators representing consistent labels then behaves exactly as the test intends. Conversely, detectable coordinate structure can be decoded into a labeling satisfying a nontrivial fraction of the original edges.

The analysis uses Fourier analysis of Boolean functions. Every real-valued function on the Boolean cube has an expansion

f(x)=∑S⊆[q]f^(S)∏i∈Sxi.f(x)=\sum_{S\subseteq[q]}\widehat f(S)\prod_{i\in S}x_i.

Under the uniform measure, the influence of coordinate ii for a Boolean-valued function can be expressed as

Inf⁡i(f)=∑S∋if^(S)2.\operatorname{Inf}_i(f)=\sum_{S\ni i}\widehat f(S)^2.

Large influence indicates that changing a particular coordinate often affects the function. A dictator concentrates all of its nonconstant Fourier weight on one coordinate. Soundness arguments frequently show that unusually successful test behavior forces substantial low-degree influence, which is then sufficient for probabilistic decoding.

A second key quantity is noise stability. If xx is uniform on the Boolean cube and yy is generated so that corresponding coordinates have correlation ρ\rho, then

Stab⁡ρ(f)=E[f(x)f(y)]=∑S⊆[q]ρ∣S∣f^(S)2.\operatorname{Stab}_{\rho}(f) =\mathbb E[f(x)f(y)] =\sum_{S\subseteq[q]}\rho^{|S|}\widehat f(S)^2.

Noise suppresses high-degree Fourier terms and makes the low-degree structure of a function especially important. For a balanced Boolean function, positive noise stability measures a tendency to retain the same output under correlated perturbations. Different reductions convert such stability or disagreement probabilities into the fraction of target constraints satisfied.

The Majority Is Stablest theorem, due to Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz, supplies a decisive bound for low-influence functions. For fixed correlation 0<ρ<10<\rho<1, balanced Boolean functions with sufficiently small influences cannot have noise stability substantially greater than large majority functions. Its proof uses an invariance principle relating suitable low-influence functions of independent discrete variables to functions of Gaussian variables, together with Gaussian noise-isoperimetric results. This analytic machinery explains why Gaussian halfspaces appear in sharp approximation thresholds for finite graph problems.

Sharp thresholds for Max-Cut and vertex cover

The most widely known consequence concerns Max-Cut. Given a graph with nonnegative edge weights, Max-Cut asks for a partition of the vertices maximizing the total weight of edges crossing between the two parts. Michel Goemans and David Williamson introduced a semidefinite-programming approximation algorithm in 1995. It assigns a unit vector vuv_u to each vertex and maximizes

∑uv∈Ewuv1−⟨vu,vv⟩2.\sum_{uv\in E}w_{uv}\frac{1-\langle v_u,v_v\rangle}{2}.

A random hyperplane through the origin then partitions the vectors according to which side they occupy. Two vectors at angle θ\theta are separated with probability θ/π\theta/\pi.

The resulting worst-case approximation ratio is

αGW=min⁡0<θ≤πθ/π(1−cos⁡θ)/2≈0.878567.\alpha_{\mathrm{GW}} =\min_{0<\theta\leq\pi} \frac{\theta/\pi}{(1-\cos\theta)/2} \approx 0.878567.

For a maximization problem, an approximation ratio α\alpha means that the algorithm returns a solution worth at least α\alpha times the optimum. The formula compares the expected rounded contribution of an edge with its contribution to the semidefinite relaxation. The algorithm therefore supplies a universal guarantee, not merely an empirical observation about particular graph families.

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell showed that, assuming the Unique Games Conjecture, no polynomial-time algorithm can achieve a Max-Cut approximation ratio strictly exceeding αGW\alpha_{\mathrm{GW}}, unless P=NP\mathrm P=\mathrm{NP}. Their work connects unique-game reductions to noise-stability inequalities. The same Gaussian geometry governing random-hyperplane rounding also governs the soundness of the reduction. This matching of an algorithmic guarantee and a conditional lower bound made Max-Cut a central example of the conjecture’s explanatory power.

A second major consequence concerns minimum vertex cover. A vertex cover is a set of vertices meeting every edge. A maximal matching gives a simple factor-2 approximation: choose both endpoints of every matched edge. Every vertex cover must include at least one endpoint of each matching edge, while the algorithm chooses exactly two. In 2008, Khot and Oded Regev established that, under the Unique Games Conjecture, approximation within 2−ε2-\varepsilon is NP-hard for every fixed ε>0\varepsilon>0. Here the approximation factor is stated in the minimization convention: the returned cover has size at most the factor times the optimum.

The two examples illustrate different kinds of precision. For Max-Cut, the conjecture identifies a nontrivial analytic constant associated with a sophisticated relaxation. For vertex cover, it would show that an elementary factor-2 guarantee is already optimal in the worst case, despite extensive algorithmic efforts. Neither implication makes the corresponding hardness statement unconditional. Moreover, special graph classes may admit better algorithms without conflict: a reduction proving general hardness need not produce planar graphs, bounded-treewidth graphs, or instances satisfying other favorable structural assumptions.

Semidefinite programming and general constraint satisfaction

The conjecture’s broadest algorithmic consequence comes from Prasad Raghavendra’s 2008 theorem on constraint satisfaction problems. A finite constraint language specifies a finite domain and a finite collection of allowed predicates, each involving a bounded number of variables. An instance applies those predicates to selected tuples of variables and asks for an assignment maximizing the total satisfied weight. Max-Cut, fixed-width satisfiability maximization, and many finite-domain labeling problems fit this framework.

A natural semidefinite programming relaxation represents possible labels by vectors and records locally consistent probability information about the assignments to each constraint. In an actual integral solution, each variable receives exactly one label, and the local assignment distributions are concentrated on the labels chosen. The relaxation allows fractional local behavior and geometric correlations that need not arise from any single global assignment. Its optimum is efficiently approximable to the precision needed for fixed-parameter approximation guarantees, but it can exceed the true optimum.

The difference between these two optima is an integrality gap. If a maximization instance has true optimum at most ss while the relaxation has value at least cc, the pair (c,s)(c,s) records a limitation of the relaxation. Ordinarily, such a gap proves only that a particular mathematical relaxation is imperfect. It does not rule out an unrelated algorithm that uses entirely different information. Raghavendra’s result establishes, under the Unique Games Conjecture, a much stronger connection between these geometric gaps and computational hardness.

Informally, for every fixed finite constraint language, an appropriate rounding of its basic semidefinite relaxation achieves the optimal polynomial-time approximation guarantee, up to arbitrarily small additive losses, assuming the conjecture and the usual complexity separation. Correspondingly, integrality-gap instances for this relaxation can be transformed into conditional hardness results. The theorem is often described as saying that semidefinite programming is optimal for every constraint satisfaction problem. The qualification matters: it refers to this finite-domain, bounded-arity approximation framework, not to every optimization problem expressible using constraints.

One reason for the theorem’s generality is that both its algorithmic and hardness sides can be expressed through related Gaussian rounding constructions. Local distributions from the relaxation determine correlated random inputs. Rounding functions translate these inputs into domain labels. On the hardness side, analogous functions appear in dictatorship tests, where low-influence behavior is compared with the same geometric model. The proof thus turns a recurring correspondence in individual problems into a general principle.

The result does not automatically give a simple formula for every optimal approximation ratio, nor an efficient practical implementation of every rounding scheme. Constants and preprocessing can depend heavily on the predicate language and desired accuracy. It also does not classify all minimization problems, all unbounded-domain problems, or all instances where arity grows with input size. Within its scope, however, it explains why apparently unrelated approximation thresholds repeatedly align with the performance of a common semidefinite relaxation.

Algorithms for unique games

The uniqueness condition makes unique games more tractable than arbitrary constraint systems in several important settings. Exact satisfiability is easy, and a two-label permutation constraint is either equality or inequality. The latter case is closely related to Max-Cut, while mixtures of equality and inequality give signed binary constraint problems. These observations do not refute the conjecture because its strongest gap requires an alphabet that can grow with the chosen error parameters. They nevertheless show that the local form of the constraints imposes substantial algorithmic structure.

Semidefinite relaxations exploit that structure by assigning a vector vu,av_{u,a} to each possible label aa at a vertex uu. Orthogonality and normalization conditions model the selection of one label, while the edge objective rewards agreement between vu,av_{u,a} and vv,πuv(a)v_{v,\pi_{uv}(a)}. Rounding must turn these compatible-looking vectors into one label per vertex. Near-perfect relaxed value gives useful geometric information, but the challenge is to convert it into globally consistent choices without losing too much as the alphabet grows.

Graph expansion provides additional leverage. In an expanding graph, no substantial vertex set has very few edges leaving it. Good local consistency then constrains much of the graph rather than remaining confined to a weakly connected region. Algorithms based on propagation, spectral information, and semidefinite rounding can obtain strong guarantees on appropriate classes of expanding unique-game instances. In a general graph, a small set of problematic edges or a collection of sparse boundaries can separate regions whose locally consistent labelings are difficult to reconcile.

A major general algorithmic result is due to Sanjeev Arora, Boaz Barak, and David Steurer in 2010. Their subexponential-time algorithms distinguish sufficiently nearly satisfiable unique games from instances of much lower value. A representative consequence is that, for every fixed α>0\alpha>0, a suitable completeness parameter allows such a distinction in time of the form

exp⁡(nα),\exp(n^\alpha),

up to additional polynomial factors and parameter-dependent details, where nn measures the size of the constraint graph. This is much faster than enumerating all qnq^n assignments, but it remains superpolynomial for fixed positive α\alpha.

The distinction between polynomial and subexponential time is essential. NP-hardness does not by itself exclude subexponential algorithms, so these results are compatible with the conjecture. They do indicate that unique games occupy an unusual algorithmic position: the conjectured hardness survives despite methods substantially faster than exhaustive search. They also constrain overly strong reductions from problems believed to require exponential time. A reduction preserving input size too closely could transfer the subexponential algorithm to its source problem.

More powerful sum-of-squares relaxations provide another line of investigation. Higher levels impose increasingly extensive consistency conditions and can defeat examples that fool weaker relaxations. Some proposed hard instances for basic semidefinite programming are therefore insufficient as evidence for computational hardness. Conversely, proving gaps for several levels of a hierarchy rules out a family of relaxation-based approaches, not every polynomial-time algorithm. Algorithmic successes and hierarchy lower bounds address different parts of the conjecture’s difficulty.

Related conjectures and proved variants

The original conjecture belongs to a family of hypotheses about projection constraints, graph expansion, and restricted verification systems. These statements often have related consequences, but their parameters and completeness conditions must be distinguished carefully. In particular, a theorem about a related game need not settle unique games: a reduction may lose too much completeness, introduce a different kind of constraint, or preserve only one direction of implication.

A prominent relative is the Small-Set Expansion Hypothesis, formulated by Prasad Raghavendra and David Steurer in 2010. For a regular graph and a vertex set SS, its edge expansion is the proportion of edges incident from SS that leave SS, with the appropriate degree normalization. Roughly, the hypothesis asserts that, for suitable small constant set sizes, it is hard to distinguish a graph containing a small poorly expanding set from a graph in which all sets of that size expand very well. The hidden object is a cluster rather than a labeling, but both problems involve globally detecting structure that may be obscured by local ambiguity.

Small-set expansion provides a geometric explanation for difficulties encountered by unique-game algorithms: a labeling may behave consistently inside regions separated by sparse boundaries. The hypothesis implies the Unique Games Conjecture through known reductions and supports hardness results for graph partitioning problems. The reverse implication is not known in its standard form. Describing the two hypotheses as interchangeable would therefore erase a substantive unresolved distinction.

Another family consists of dd-to-dd games. In a unique game, every label at one endpoint has exactly one satisfying partner at the other. In a dd-to-dd game, each label has exactly dd satisfying partners in both directions. The case d=2d=2 permits only a small amount of local ambiguity beyond uniqueness, but that additional freedom changes the available hardness constructions significantly.

Work by Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra led to a 2018 proof by Khot, Minzer, and Safra of the 2-to-2 Games Conjecture with imperfect completeness. The proof uses sophisticated expansion and structural analysis of graphs built from linear subspaces, including Grassmann graphs. This was a major unconditional advance in hardness of approximation. Nevertheless, a 2-to-2 constraint is not a permutation constraint. Converting it to unique constraints can sacrifice the near-perfect completeness needed for the original Unique Games Conjecture.

The phrase “with imperfect completeness” is also important. A promise that the optimum is at least 1−ε1-\varepsilon is different from a promise that it is exactly 11. In unique games, exact satisfiability is polynomial-time decidable; in other game systems it may remain computationally hard. Results must therefore be compared using their full constraint type and gap parameters, rather than only their informal names. The proved 2-to-2 result strengthens the surrounding theory without removing the unresolved requirement of simultaneous uniqueness and almost-perfect completeness.

Evidence, complexity assumptions, and unresolved directions

One source of support for the conjecture is the repeated agreement between conditional hardness bounds and independently developed algorithms. The Max-Cut threshold is a particularly precise example, while Raghavendra’s theorem extends the correspondence across finite constraint languages. Such agreement is mathematically informative: the conjecture explains many approximation phenomena through one hypothesis. It is not deductive evidence that the hypothesis must be true. A collection of elegant consequences can follow from a false assumption, and different problems could have different unconditional thresholds.

The main proof challenge is to construct sufficiently strong hardness reductions while preserving nearly satisfiable permutation constraints. General Label Cover reductions have more freedom because their projections need not be invertible. Unique constraints remove that freedom, and ordinary methods of amplifying a gap can disrupt uniqueness or lose the completeness needed for subsequent reductions. Progress on neighboring game problems shows that powerful algebraic and analytic constructions are possible, but obtaining the exact combination demanded by unique games remains a separate task.

On the algorithmic side, a refutation would require the right uniformity across alphabet sizes and gap parameters. Solving binary games, particular graph families, or selected examples with high optimum is not enough. A polynomial-time algorithm contradicting the conjecture must distinguish an appropriate near-perfect-completeness gap for every fixed alphabet relevant to that gap. The polynomial’s constants or exponent may depend on the fixed alphabet; the essential issue is polynomial dependence on the growing input size. This quantifier structure explains why substantial special-case algorithms can coexist with an unresolved conjecture.

The relation to the Exponential Time Hypothesis is another open structural issue. That hypothesis posits an exponential-time barrier for satisfiability, whereas the Unique Games Conjecture asserts a polynomial-time hardness barrier for a particular family of approximation gaps. The subexponential algorithms for unique games make size bounds in reductions especially consequential. A hypothetical reduction from satisfiability that was both sufficiently size-efficient and preserved a suitable unique-game gap could conflict with the Exponential Time Hypothesis. Ordinary polynomial reductions may enlarge the input too much for that argument to apply.

Randomization and computational models also require separate treatment. NP-hardness, combined with P≠NP\mathrm P\ne\mathrm{NP}, excludes deterministic polynomial-time algorithms for the promised distinction. Excluding bounded-error randomized polynomial-time algorithms normally requires an assumption such as NP⊈BPP\mathrm{NP}\nsubseteq\mathrm{BPP}. Likewise, the classical conjecture does not automatically establish lower bounds against quantum computation. The relevant complexity assumption must match the kind of algorithm being ruled out.

A further direction is to identify exactly which geometric obstructions can survive all efficiently enforceable consistency tests. Basic semidefinite gaps, low-level hierarchy gaps, sparse cuts, and noisy Gaussian constructions each expose a different limitation. A complete hardness proof would have to convert suitable obstructions into a reduction from an established NP-hard problem. A general algorithmic refutation would instead have to find structure that remains accessible even in instances designed to hide it. The gap between these two possibilities is the central unresolved technical content of the conjecture.