The 2-to-1 Games Conjecture with perfect completeness

← All digests

Family 105 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-08

“Almost every constraint can be satisfied” sounds close to “every constraint can be satisfied.” In approximation complexity, that final step can change which problems a theorem can address. Family 105 claims hardness for exactly two-to-one constraint systems with perfect completeness: the good instances have a solution satisfying every rule, while the bad instances permit only an arbitrarily small fixed fraction to be satisfied.

1. The question

Suppose two people must answer related questions without communicating. One receives a question from a left-hand list and the other a question from a right-hand list. Each permitted pair of questions comes with a rule translating the left answer into the required right answer.

In a two-to-one game, every possible right answer has exactly two compatible left answers. The question is whether it remains hard to distinguish two extremes: a single consistent answering scheme that always succeeds, and a situation in which every scheme fails on nearly all question pairs.

The perfect-completeness requirement concerns the first extreme. It preserves a completely satisfying assignment through the reduction. That makes it useful for problems whose inputs are promised to possess an exact structure, such as a valid coloring with a small number of colors.

2. Background and essential definitions

A constraint system described as a game

Take a bipartite graph with left vertices $U$ and right vertices $V$. Vertices represent questions. An edge occurrence $e=(u,v)$ carries a function

$$\pi_e:[2q]\longrightarrow[q], \qquad [m]=\{1,2,\ldots,m\}.$$

A labeling gives each left vertex a symbol from $[2q]$ and each right vertex a symbol from $[q]$. The constraint is satisfied when

$$\pi_e(a(u))=b(v).$$

The exact two-to-one condition says

$$|\pi_e^{-1}(j)|=2 \quad\text{for every right label }j.$$

For instance, a map from $\{1,2,3,4\}$ to $\{1,2\}$ may send 1 and 2 to 1, and 3 and 4 to 2. Another edge may pair the labels differently. The difficulty comes from using one answer per vertex across all incident edges.

The game value $\operatorname{val}(G)$ is the maximum fraction of edge occurrences that a labeling satisfies. Repeated occurrences count separately. “Unweighted” here means each listed occurrence counts equally; it does not imply that the underlying bipartite graph has no parallel edges.

The two-person language emphasizes local information. The left answer depends only on the left question, and the right answer only on the right question. Allowing either player to see the whole sampled edge could destroy the intended constraint problem.

Completeness, soundness, and hardness

A reduction transforms a source decision problem into a game. Its completeness specifies how well a labeling can do when the source answer is yes. Its soundness bounds every labeling’s success when the source answer is no.

Perfect completeness is the exact statement $\operatorname{val}(G)=1$ in the yes-case. Soundness $\delta$ means $\operatorname{val}(G)\le\delta$ in the no-case. The target is a promise problem: inputs with intermediate values do not need to be classified.

A deterministic polynomial-time reduction from 3SAT establishes NP-hardness. Here 3SAT asks whether Boolean variables can satisfy a conjunction of three-literal clauses. Consequently, an efficient algorithm distinguishing the two promised game cases would imply $\mathsf P=\mathsf{NP}$.

Why a limit does not supply perfect completeness

Suppose a sequence of constructions has completeness $1-1/r$ for every fixed integer $r$. Each finite construction may still violate some constraints. There need not be any finite output with value exactly one.

Nor does repeating a game solve both requirements automatically. Repeating an exact two-to-one constraint $t$ times produces a map on tuples in which each right tuple has $2^t$ preimages. Repetition can reduce soundness, but it loses the exact two-to-one form. Achieving low soundness, perfect completeness, and two-element fibers simultaneously is the problem.

3. Development history and previous partial results

Khot introduced the games conjectures in 2002 as sources of approximation hardness. Unique Games use permutations, so one endpoint’s label determines a unique reply. Two-to-one games allow a pair of preimages and demand perfect satisfiability in the good case. Their different completeness requirements mean that progress on one does not automatically settle the other.

Austrin, O’Donnell, Tan, and Wright obtained perfect-completeness hardness with left and right alphabets of sizes 6 and 3. Their soundness was $23/24+\varepsilon$, for arbitrarily small positive $\varepsilon$. This showed hardness under exact satisfiability, but the bad instance could still satisfy most constraints.

The Grassmann-graph and shortcode developments of 2017–2018 supplied the opposite kind of progress: completeness arbitrarily close to one and soundness arbitrarily close to zero. The work culminated in the expansion theorem of Khot, Minzer, and Safra. The unresolved endpoint was to keep every good-case constraint satisfied.

On September 14, 2026, Fei, Minzer, and Wang posted a perfect-completeness result for four-to-one games with arbitrarily small fixed soundness. Thus the relevant comparison is quite specific: family 105 claims the exact two-to-one version. It tightens the permitted constraint fibers while retaining both endpoints of the gap.

These distinctions matter for applications. A reduction that needs completely satisfiable source instances cannot simply replace that premise by arbitrarily good approximate satisfiability.

4. What the new manuscripts claim

Theorem 1.1 of the manuscript states that for every fixed rational $\delta\in(0,1)$, there is an alphabet parameter $q=q(\delta)\ge2$ and a deterministic polynomial-time reduction from a 3SAT formula $\varphi$ to a game $G_\varphi$ satisfying

$$\begin{aligned} \varphi\text{ satisfiable}&\quad\Longrightarrow\quad \operatorname{val}(G_\varphi)=1,\\ \varphi\text{ unsatisfiable}&\quad\Longrightarrow\quad \operatorname{val}(G_\varphi)\le\delta. \end{aligned}$$

Every constraint has exactly two preimages for each right label. The output lists the unweighted edge occurrences and all projection tables explicitly. The alphabet, polynomial degree, and constants may depend on $\delta$, which is chosen before the source input varies.

The paper also applies an earlier Guruswami–Sinop reduction to maximum $k$-colorable subgraph. Given a graph that really is $k$-colorable, one tries to assign $k$ colors so that as many edges as possible have differently colored endpoints. The claimed consequence rules out exceeding

$$1-\frac1k+C\frac{\log k}{k^2}$$

of the edges in the hard case, for an absolute constant $C$ and every sufficiently large fixed $k$. A uniformly random coloring succeeds on an expected fraction $1-1/k$, so the displayed correction measures a comparatively small improvement over that baseline.

A further corollary recovers hardness for satisfiable Not-Two constraints, which accept a triple of Boolean inputs unless exactly two are true. The manuscript explicitly identifies this as an alternative route to an already known result, rather than a new threshold.

5. Why the advance matters

Perfect completeness protects exact promises. A source solution can be translated into a graph coloring or another structure that satisfies every local requirement. A small proportion of source failures could otherwise become genuine defects in the target object.

The theorem would also provide a more restrictive general hardness source: every projection merges pairs, rather than arbitrary-sized groups. Restricting the local maps while preserving strong global hardness helps subsequent reductions work with cleaner constraints.

Importance: 3/5, provisional. The claimed result is a substantial advance within approximation complexity, closing the exact two-to-one, perfect-completeness gap. Its scope is narrower than the broad approximation framework of family 102, and some associated coloring consequences already follow from earlier work. The rating reflects that relative scope while recognizing the endpoint’s importance.

6. The main idea

Preserve real assignments through every encoding

The source is a clause-versus-variable consistency game. A left answer gives a satisfying assignment to a clause’s variables; a right answer supplies a bit for one variable. The test asks whether they agree. Standard PCP and repetition results provide a perfectly satisfiable good case and a small-value bad case, although the resulting maps need not yet be two-to-one.

The manuscript arranges many source questions at the leaves of a tree and builds function spaces above them. A displayed collection of binary functions partitions the possible source assignments according to their joint outputs. A legal encoded answer selects a nonempty part of this partition.

This choice makes consistency concrete: the selected outputs must all come from some actual assignment. Deleting one binary output direction merges at most two parts, producing preliminary maps with fibers of size at most two. A satisfying source assignment consistently selects its part at every stage, preserving perfect completeness. A final construction converts the preliminary maps into exact two-to-one maps and represents weights by explicit repeated occurrences.

Use algebra to recover short lists of answers

For soundness, the challenge is to interpret an arbitrary labeling that succeeds too often. The construction includes products of functions, making the response to a product related to responses to its factors.

A genuine evaluation at an assignment $x$ obeys

$$(gh)(x)=g(x)h(x).$$

If functions $s_1,\ldots,s_\ell$ are evaluated at $x$, the matrix with entries $s_i(x)s_j(x)$ is the outer product $yy^{\mathsf T}$, where $y_i=s_i(x)$. Such a matrix has rank at most one. The paper exploits this algebraic trace of genuine evaluation, using binary function spaces and matrix structure theorems.

An arbitrary answer does not have to be genuine evaluation. The proposed decoding argument seeks bounded-rank structure that yields short lists of candidate source answers. It then compares lists on opposite sides of source constraints. If too many pairs are compatible, choosing answers from the lists would beat the source game’s soundness bound.

Keep the information local

It is not enough to extract a useful list after seeing an entire constraint. Each side must construct its list using only its own question. Otherwise the decoding would not produce a legal source labeling.

The tree sampling and projection comparisons are designed to preserve that locality. The manuscript also handles a dependence problem: a response may be chosen using the same rows on which it is tested, so passing a low-rank test alone does not control its full structure. Resampling and a second structural argument are used before decoding. This explains why the proof requires more than the elementary observation about rank-one evaluation matrices.

7. Scope, limitations, and open questions

The alphabet is fixed once the soundness target is fixed. The theorem does not say that one tiny alphabet achieves arbitrarily small soundness, nor that the reduction is polynomial uniformly when $\delta$ is supplied as a varying input parameter.

It concerns ordinary two-to-one games. A Rich two-to-one game imposes an additional distributional condition: around each left vertex, the partitions into label pairs must occur uniformly. That property is not part of the stated conclusion, so applications requiring it need an additional premise.

The listed constraints form a multiset. “Explicit and unweighted” should therefore not be strengthened to “a simple graph” without a separate construction.

Finally, the result is a hardness statement, with the usual interpretation conditional on $\mathsf P\ne\mathsf{NP}$. It does not settle the most useful quantitative bounds on alphabet size, reduction size, or the behavior of restricted input families. Those questions can matter even after a qualitative conjecture is resolved.

8. Sources and further reading

Perfect completeness for 2-to-1 games, credited to OpenAI, September 23, 2026. Theorem 1.1 states the main claim; Section 1.2 explains the construction; Corollaries 1.2–1.3 give applications.

Historical sources are linked in Section 3. Optional background: Label Cover, the PCP theorem, and matrix rank.

Source revision: adc7f1241b42. Sources consulted: October 8, 2026. Citation data: BibTeX.

See the series’ AI declaration for authorship and review status. Back to the family index.