Perfect completeness for two-to-one games

Source and verification

This article explains family 105 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Projection constraints and exact fibers

A projection game has a finite bipartite multigraph with left vertices $U$, right vertices $V$, and a nonempty list of edge occurrences. Each vertex receives a label. An edge $e=(u,v)$ carries a map ${\pi }_e$ and accepts when

$${\pi }_e(a(u))=b(v).$$

The value is the maximum fraction of satisfied occurrences. Parallel occurrences may carry different maps and are counted separately. A two-to-one game has common alphabets $[2q]$ and $[q]$ and requires

$$\begin{array}{c}|{\pi }_e^{-1}(b)|=2\\ (e\in E,b\in [q]).\end{array}$$

For instance, the map $1,2\mapsto 1$ and $3,4\mapsto 2$ has exact two-element fibers. The condition constrains each individual table, rather than an average over tables.

Perfect completeness means that every YES instance has one labeling satisfying every edge. Soundness at most $\delta$ means that every labeling of a NO instance satisfies at most a $\delta$ fraction. A sequence of reductions with YES values approaching one does not imply this exact endpoint for any finite output.

🏷️ The claimed reduction

Manuscript statement

For each fixed rational $0<\delta <1$, there is a fixed $q=q(\delta )\ge 2$ and a deterministic polynomial-time reduction from 3SAT to explicit unweighted two-to-one games with

$$\begin{array}{rl}\text{YES}:& \mathrm{val}=1,\\ \text{NO}:& \mathrm{val}\le \delta .\end{array}$$

Every table has exactly two preimages per right label. The output contains its full nonempty edge list and projection tables. The polynomial and alphabets may depend on the fixed soundness target. (OpenAI, 2026)

For a real positive soundness target one can use a smaller fixed rational target. The statement concerns ordinary two-to-one games. It does not impose the additional “Rich” condition that the incident edges at each left vertex induce a uniform distribution over all pair partitions of its alphabet.

🏷️ Why straightforward repetition is insufficient

Repeating a projection constraint independently $k$ times asks for a tuple of left labels and a tuple of right labels. Each right tuple then has $2^k$ left preimages. Repetition can reduce acceptance on NO instances but changes the fiber size. It cannot by itself supply small soundness while retaining exactly two replies.

The source instead begins with a perfectly complete projection-game gap and places independent questions at leaves of a finite tree. At a leaf, consider binary-valued functions on its possible answers. Higher nodes contain spaces generated by products of lower functions. Arrays of such functions partition the full product answer domain according to their joint evaluations.

A legal answer is a nonempty part of that joint partition. It is therefore realized by one underlying assignment, simultaneously for all displayed arrays. Erasing one binary output direction merges at most two parts, giving preliminary projections with fibers of size at most two. A satisfying source labeling evaluates every array consistently, preserving completeness exactly throughout the construction.

Joint legality is stronger than checking each row independently. If a restored linear functional $z$ satisfies $z(1)=1$ and defines a product form $F(g,h)=z(gh)$, then lower rows $s_1,\dots ,s_{\ell }$ with restored answer $y$ obey

$$(F(s_t,s_u){)}_{t,u}=y{y}^{\mathsf{T}}.$$

The tested matrix has rank at most one. The spaces and product forms here are tools for a finite constraint test; this note does not develop their general algebraic theory.

🏷️ The soundness chain and its dependence problem

The sampler singles out a random root-to-leaf path, with fresh randomness for every recursive call. Many children hide the special path child. A second comparison sparsely replaces left questions by projected right questions. Both comparisons require bounds on the joint distributions seen by later decoders, including a bound on selecting a projected child after observing the sampled functions.

If a labeling passes a positive fraction of the preliminary constraints, some pair of levels has positive joint success. An inverse theorem for the matrix test finds a response appearing densely on an affine slice. Its constants must be independent of the response range, since an upper response records many descendants. This yields candidate product forms agreeing across a projection with positive probability.

There is a crucial dependence issue: the candidate form was selected using the very rows on which its rank is tested. Passing a rank-one test on those rows does not show that the form has low full rank. The paper resamples within a fiber where one output direction is omitted, upgrades agreement of restrictions to agreement of full forms, and applies a second inverse argument. Only after isolating a fixed form on a sufficiently dense slice does the small probability of a high-rank form passing the test become applicable.

A bounded-rank normalized form supplies a short odd list of answers at each source leaf. Under projection, retain those right answers with an odd number of left preimages. This is a parity pushforward, not ordinary set image: two colliding list entries cancel. An odd-size list still has a nonempty parity pushforward, since the sum of its fiber cardinalities is odd.

On certain projected children, every sampled contribution vanishes. Conditioning on this event preserves the original independent source-question distribution because its probability is exactly independent of those questions. The decoders can reconstruct their inputs from their own questions there. Repetition bounds agreement on these coordinates, contradicting the positive agreement derived from the two inverse steps. The local information restriction is essential to obtaining legitimate source-game strategies.

🏷️ Completing at-most-two maps without losing the gap

The final exact-fiber step is a useful finite calculation. Suppose a preliminary edge has legal labels $L,R$ and a map $\pi :L\to R$ whose fibers have size at most two. Embed these labels in common alphabets $[2q],[q]$. For each right label let

$$c_b=2-|{\pi }^{-1}(b)|.$$

Labels outside $R$ initially have no preimages. There are $N=2q-|L|$ new left labels, and ${\sum }_b{c}_b=N$. Enumerate all ways to assign these new labels to the remaining capacities, giving completions equal conditional weight.

Every completed map is exactly two-to-one and agrees with $\pi$ on legal labels. For a fixed new left label $a$ and fixed right label $b$, symmetry gives

$$\mathrm{Pr}[\hat{\pi }(a)=b]=\frac{c_b}{N}\le \frac{2}{N}.$$

Choose $q$ so large that $2/N\le \delta /3$ uniformly over preliminary edges. Any labeling’s satisfaction using two legal endpoints is bounded by the preliminary soundness; its additional success using an illegal left label is at most $\delta /3$. Legal-left/illegal-right pairs never accept. In the YES case, the original legal labeling satisfies every completion, so completeness remains exactly one.

Finally rational edge weights are replaced by explicitly listed occurrences with controlled rounding error. All local alphabets, tree sizes, and completion counts are constants once $\delta$ is fixed. Enumerating these potentially enormous finite objects is therefore polynomial in input size for that fixed target, without a randomized reduction.

🏷️ A coloring consequence with fixed parameters

The manuscript applies the result to maximum $k$-colorable subgraph. Given a coloring by $k$ colors, count the fraction of edges whose endpoint colors differ. For all sufficiently large fixed $k$, it derives hardness of distinguishing a $k$-colorable graph from one where every such coloring properly colors at most

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

of its edges, for an absolute $C$. The baseline $1-1/k$ comes from assigning independent uniform colors: an edge is monochromatic with probability $1/k$. The result concerns the fraction of edges retained, not the number of colors needed to color the entire NO graph.

The paper also recovers consequences for satisfiable three-query predicates and constant-palette coloring that it identifies as already known through other inputs. These are applications of the new premise, not claims that every listed consequence is itself new.

🏷️ Key steps and proof outlines

Resampling before conditioning on success

The central difficulty in “From tested rank to full rank” is adaptive selection: a decoder sees sampled rows $S$ and then chooses a form $F_S$. A low-rank Gram matrix for $F_S$ on those same rows need not imply that $F_S$ has low rank on the whole space. The source removes this dependence through two independent draws inside one quotient fiber. (OpenAI, 2026)

Fix the background information and the erased output direction $a$. The right decoder sees the quotient $q=S\mathrm{mod}a$ and therefore returns one fixed answer on that fiber. Let $p(q)$ be the conditional probability that the left answer agrees with it. For two independent fiber draws $S,S^{\prime }$,

$$\mathrm{Pr}[\text{both agree}]=\mathbb{E}[p(q{)}^2]\ge (\mathbb{E}p(q){)}^2=h^2,$$

where $h$ is the original agreement probability. The inequality is the nonnegativity of variance. Before inspecting either success event, the pair also has the representation $S^{\prime }=S+al$ with $l$ uniform in the lower function space. Thus positive two-decoder agreement becomes equality of one table under a rank-one perturbation.

Agreement of restrictions is not yet equality of full forms. A separate posterior estimate bounds the probability that two different forms become equal only after sparse projection. Total-variation comparison then transfers the experiment to unrestricted uniform rows. In the source’s notation the resulting lower bound is

$$h^2-\frac{2\beta L}{1-\beta }-\upsilon .$$

Here $\beta$ is the sparse-projection probability, $L$ a likelihood-ratio bound for the exposed child data, and $\upsilon$ the total-variation error. These losses are chosen smaller than a fixed fraction of $h^2$. Crucially, the comparison uses the unfiltered pair distribution; conditioning first on successful decoding could reveal the hidden projection flags and invalidate the posterior bound.

A fixed high-rank form rarely passes the rank-one test

Rank test on an affine slice

After a bounded number $r^{\prime }$ of row and column constraints, a fixed form of rank $R$ retains rank at least $R-2r^{\prime }$ on the free direction space. Two disjoint groups of $m$ free rows then test it through an $m\times m$ cross matrix.

To prove the rank loss, let $N$ be the common kernel of the column constraints. Its codimension is at most $r^{\prime }$. Restricting the first argument to $N$ loses at most $r^{\prime }$ in rank, and restricting the second argument loses at most another $r^{\prime }$. An invertible row change isolates the prescribed row combinations, leaving independent rows on affine translates of $N$.

Take the first $m$ free rows $x_1,\dots ,x_m$. They define linear functionals $F(x_i,\cdot ){|}_N$. For any nonzero binary coefficient vector, their linear combination is uniform on a translate of a space of dimension at least $R-2r^{\prime }$. Its probability of vanishing is at most $2^{-(R-2r^{\prime })}$. A union bound over the $2^m-1$ nonzero coefficient vectors bounds the chance of dependence.

If these functionals are independent, each fresh row from the second group gives a uniform column in ${\mathbb{F}}_2^m$. The cross matrix is therefore uniform among $2^{m^2}$ matrices. Exactly $1+(2^m-1{)}^2$ have rank at most one: the zero matrix and the distinct outer products of two nonzero binary vectors. Hence

$$\begin{array}{rl}\mathrm{Pr}[\mathrm{rank}{\mathrm{Gram}}_F(S)\le 1]& \le (2^m-1)2^{-(R-2r^{\prime })}\\ & +[1+(2^m-1{)}^2]2^{-m^2}.\end{array}$$

Choose $m$ first so the second term is small, then $R$ sufficiently large so the first is small. The inverse theorem supplies a fixed form appearing with positive density on a slice; the displayed estimate excludes high rank for that fixed form. This is why the proof needs another inverse step after resampling, rather than applying a rank bound directly to an adaptively chosen output.

The bounded-rank forms now yield short odd lists. Their parity pushforwards remain nonempty, allowing local strategies on clean source coordinates. Independent repetition bounds those strategies’ agreement from above, while the preceding extraction bounds it from below. Exact-two completion is performed only after this soundness contradiction, preserving the perfectly satisfying labeling throughout.

See Also

• Unique Games and approximation gaps asks for a unique reply with completeness near one, a different endpoint from exact two-to-one perfect completeness.
• Three-colorability and independence density proves a stronger independent-set soundness statement for three-colorable YES graphs by a separate route.

🏷️ Manuscripts and verification scope

• Perfect completeness for 2-to-1 games — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The stated scope is the exact-two, perfectly complete reduction for every fixed rational soundness target, with time measured in the original input bit length. It does not assert the Rich condition. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Perfect completeness for 2-to-1 games.