Unique Games conjecture

Put a 0 or 1 on each of three dots joined in a triangle. Two connections require equal labels; the third requires opposite labels. Any labelling must break a rule, but it can obey two of the three. Each rule fixes one endpoint’s label once the other is chosen. Unique Games asks whether much larger puzzles can be hard to distinguish when almost all rules are obeyable in one case, but only a tiny fraction in the other.[1] [2]

A Unique Game assigns one label from a finite set to each dot of a graph. An edge pairs the labels by a permutation, so either endpoint’s label determines exactly one allowed label at the other. Write $\operatorname{OPT}(U)$ for the largest fraction of satisfied edges over all labellings. For every pair of positive constants $\varepsilon,\delta$ with $1-\varepsilon>\delta$, the standard conjecture predicts a sufficiently large finite alphabet size $k=k(\varepsilon,\delta)$ for which distinguishing $\operatorname{OPT}(U)\ge 1-\varepsilon$ from $\operatorname{OPT}(U)\le\delta$ is NP-hard. The alphabet is fixed after those error tolerances are chosen; the graph size then grows. Instances between the two thresholds are outside the promise.[1] [2]

The triangle is an easy illustration, not evidence of hardness. The standard conjecture remains unproved; its label set can be much larger than two. A related proved result allows two matching labels on a connection, changing the puzzle’s rules.[1] [2]

A proof must establish this near-satisfiable-versus-low-value gap with one-to-one edge matches; an algorithmic challenge to the conjecture must handle its error parameters rather than just solve the two-label triangle. The 2025 article explains the completed 2-to-2 line of work with imperfect completeness. A 2-to-2 edge allows two compatible labels for a chosen label, unlike the unique match here; that milestone does not prove the standard conjecture.[1] [2]

The question connects label puzzles to the quality of approximate answers elsewhere. For example, finding the smallest set of dots touching every connection is the vertex-cover problem. A fast method uses at most twice the minimum number; Unique Games would make a fixed improvement on that universal guarantee computationally hard.[2] [3]

A reduction can translate the label-puzzle gap into vertex-cover instances with separated optimum sizes. This transfers a hardness claim about recognizing the puzzle to a limit on constructing near-optimal covers. Under Unique Games and $P\ne NP$, no deterministic polynomial-time algorithm guarantees a fixed approximation factor below two on every graph. The issue is whether a familiar efficient guarantee marks a fundamental worst-case boundary, rather than a ceiling imposed by current algorithm design.[2] [3]