OpenAI's Unique Games claim: repairing the completeness gap

On this page

Scientific progress includes learning which promises can be kept. In computer science, an impossibility theorem can rule out a universal algorithmic guarantee while leaving many useful practical solutions open. OpenAI's Unique Games claim would be that kind of discovery. Under the assumption that P differs from NP, it would strengthen our account of computation's limits. We think that is an important part of what increasingly capable research agents should help us understand.

In 2002, Subhash Khot asked whether a network of constraints could remain hard to solve even when almost all its rules could be satisfied together. An answer at one end of an edge uniquely determines the compatible answer at the other. Twenty-four years later, OpenAI's 6 October mathematics release includes a model-attributed manuscript claiming to prove the conjecture. The result would help establish the best possible approximation guarantees for other problems.

Earlier work had reached a related result with roughly half the constraints satisfiable in the favourable case. The full conjecture needs that case to be almost completely satisfiable. We followed this gap through the older matrix encoding, OpenAI's replacement and the released reasoning summary about BasicSDP hardness. The reported failures and repairs reveal the specific inventive work behind a claim with much wider consequences for how computer scientists direct their efforts.

Four edges show why local answers can fail

Take four vertices around a cycle: A, B, C and D. Give each a label, either 0 or 1. Three edges demand equality: $A=B$, $B=C$ and $C=D$. The last demands $D\ne A$.

Every edge has exactly one compatible answer once the label at its other end is known. Together, the rules conflict. The three equality edges bring us back to the starting label; the final edge asks us to flip it.

We checked all 16 assignments. The best satisfy three edges, so the value is 3/4. This is an easy example, not a hardness experiment. It gives us the central problem in miniature: uniquely determined local choices can still resist a globally consistent answer.

A Unique Games instance generalises that setup. Each edge carries a permutation of a finite label alphabet. The objective is to satisfy the largest fraction of edges. Subhash Khot's survey sets out the formal problem.

The small cycle is useful for understanding the name. The claimed theorem demands something much more surprising.

The conjecture grew out of a question about approximation

Subhash Khot introduced the conjecture in 2002. Finding exact answers to many optimisation problems was already known to be NP-hard. The field wanted to understand how much difficulty survived when we accepted an approximate answer. Could a fast algorithm always get closer to the optimum, or did some familiar guarantees mark a genuine limit?

Khot's conjecture offered a common source of hardness from which researchers could derive limits for other problems. That is why a rather artificial-looking network of labels became important. Its consequences reached algorithms that people actually understood and used.

There was substantial progress before OpenAI. A line of work involving Irit Dinur, Khot, Guy Kindler, Dor Minzer and Muli Safra culminated in the 2018 proof of the related 2-to-2 Games conjecture with imperfect completeness. Khot's 2019 account explains the resulting Unique Games gap: roughly half the constraints can be satisfied in the favourable case, against an arbitrarily small fraction in the unfavourable one. The full conjecture asks for the favourable case to be almost completely satisfiable.

We find that distinction more revealing than a claim to have finished a famous problem. The new manuscript must close a specific gap that the earlier breakthrough left open.

The claim is a gulf between 99% and 1%

OpenAI's Theorem 1.1 chooses any fixed positive $\varepsilon$ and $\delta$ below $1/2$. It supplies a finite alphabet of size $2^s$ and a deterministic polynomial-time reduction from 3SAT. A satisfiable formula produces a game with value at least $1-\varepsilon$. An unsatisfiable formula produces one with value at most $\delta$.

Use 1% for each tolerance. The reduction would separate games where some assignment satisfies at least 99% of the constraints from games where every assignment satisfies at most 1%. Distinguishing those cases would be NP-hard. The alphabet can be large, but after the tolerances are chosen it stays fixed, independently of the input formula's length. The paper even restricts its output to simple bipartite graphs with binary-vector-space translation constraints.

We think that gulf is the heart of the announcement. Our cycle shows a conflict. The theorem needs a systematic construction whose almost perfect and almost hopeless cases remain hard to tell apart.

Why not require 100% satisfiability? Because perfect consistency can be checked by propagating labels through a connected component and trying its possible starting labels. A scattering of permitted errors defeats that simple check. Khot and Regev discuss the importance of positive completeness error.

The tolerances aren't small print. They define the problem the proof claims to solve.

The familiar approximation limits would become firmer

Consider Max-Cut: divide a graph's vertices into two groups so that as many edges as possible cross between them. Michel Goemans and David Williamson's 1995 algorithm relaxes binary choices to unit vectors, then rounds with a random hyperplane. Its guarantee is approximately 0.878567 of the optimal cut, in expectation and with arbitrarily small numerical tolerance.

The geometry explains the number. Vectors at angle $\theta$ are separated with probability $\theta/\pi$, while contributing $(1-\cos\theta)/2$ to the relaxed objective. At 120 degrees the ratio is 8/9; the worst angle gives the slightly smaller constant.

Khot, Kindler, Mossel and O'Donnell showed that Unique Games implies hardness above that threshold. Khot and Regev supplied the corresponding factor-two barrier for Vertex Cover, the task of choosing the smallest set of vertices meeting every edge.

Vertex Cover's simple factor-two algorithm takes both endpoints of every edge in a maximal matching. Any cover needs at least one endpoint per matched edge, so the answer uses at most twice the optimum. Under the conjectured hardness, beating that factor by a fixed amount on every input is NP-hard.

A valid Unique Games theorem would remove the conjectural premise from these implications. Assuming $\mathrm{P}\ne\mathrm{NP}$, it would exclude deterministic polynomial-time algorithms with a fixed Max-Cut ratio above the Goemans–Williamson constant or a fixed Vertex Cover factor below two. It would not prove $\mathrm{P}\ne\mathrm{NP}$ itself.

We see a compelling kind of progress here: explaining why a familiar algorithm has a guarantee that appears stubbornly hard to improve.

The proposed encoding has to earn the conclusion

The construction has to preserve good answers while making false success informative. An encoding represents an intended answer as a larger table or function on which the reduction can run local tests. If the tests accept an arbitrary dishonest table too easily, the reduction has lost the hardness it was meant to transfer.

Barak, Kothari and Steurer's 2018 construction makes the obstacle tangible. It represents answers using binary matrices and changes a matrix by a rank-one update, a structured change built from two vectors. In the local test, the intended answer can stay as it was or shift by a specified amount. Allow both replies and the honest answer survives. Require the unchanged answer alone, making the reply unique, and it survives only about half the time.

The authors considered higher-degree tensor tests to improve that probability. But those larger tests could not simply be inserted into the surrounding proof system: their growth exceeded what the composition could accommodate. OpenAI's manuscript proposes to retain the established degree-two analysis and change the perturbation instead.

The proposed replacement uses a nonlinear map built recursively from quadratic blocks. It is designed so that the evaluation associated with an intended answer hardly changes under the new perturbation. At the same time, linear measurements that remain sufficiently independent on the output-translation directions—the directions corresponding to changes in the encoded label—must still detect that perturbation. That separation is the mechanism: almost perfect stability for the intended nonlinear evaluation, without hiding the change from the linear analysis needed to examine arbitrary answers.

Overlapping tests also share exact table keys, forcing a purported answer to give the same response wherever the same part appears. The construction overview uses that consistency to connect the new noise construction back to the inherited degree-two theorem. Both the noise and the way it fits the surrounding reduction have to work.

The other half of the proof asks what happens if a table passes too often in an instance that should be almost impossible to satisfy. The proposed analysis extracts short lists of answers to the original problem and a separate decoding rule. One side selects from a list; the other decodes using its own available information. Their answers must agree more often than is possible in such an unfavourable instance. Repeated testing supplies the incompatible upper bound. That contradiction would show that no dishonest table can pass often enough to destroy the promised gap.

The released reasoning summary about BasicSDP hardness reports a related search with Unique Games as an intermediate target. In early sparse and tensor-noise attempts, the test exposes a projection that a dishonest strategy can use to adapt its reply. A Gaussian-smoothing route leaves dishonest responses stable too. The later quadratic construction tries to preserve the intended evaluation while keeping enough detectable linear structure to constrain those responses.

A second problem appears in decoding. Finding agreement on an exceptionally rare set of tables is insufficient: the argument needs enough such cases under the actual sampling rule to get a useful lower bound on agreement. The reported search develops exact shared keys and an abundance argument to address that gap, then checks that its choices remain uniform as dimensions grow.

The supplied original question concerns ordinary NP-hardness at semidefinite approximation thresholds without assuming Unique Games. The conjecture becomes an intermediate target. That matters when reconstructing the search: the displayed question did not simply ask the model to prove Khot's conjecture.

That is more revealing about research than saying the model found a proof. The account identifies a failed mechanism and attempts to redesign it around two competing demands. It remains OpenAI's abridged account; we haven't certified the construction or reproduced the search.

The release also contains direct Max-Cut and Vertex Cover manuscripts. Their separate reductions need separate scrutiny. Multiple related conclusions do not independently verify a shared mechanism.

Discovery can establish a limit

A valid Unique Games proof would strengthen the reasons certain approximation guarantees resist universal improvement under $\mathrm{P}\ne\mathrm{NP}$. For researchers, that would help distinguish a limit requiring a change of assumptions from an algorithm that merely needs a better design. Practical optimisation on structured instances, longer running times and other computational tradeoffs would remain open. Arora, Barak and Steurer's subexponential algorithms already illustrate that distinction.

The research task visible in the release is inventive. It retains the useful part of an older construction, identifies where it fails, and redesigns the encoding so two competing requirements can both hold. An agent contributing reliably to that work could help establish limits that apply to other algorithms, including algorithms developed with AI. Greater inventive capability would not repeal the theorem's assumptions or escape its conclusion for an algorithm operating within them.

That gives the wider scientific story a useful discipline. We should ask research systems to improve our account of what is achievable, including where a goal needs to be reformulated. A hardness theorem can redirect effort towards a restricted problem, a weaker guarantee or a different use of computation. It can make a research programme more informed without producing a faster solver. Those choices matter to the people doing the research and to those deciding which approaches deserve support.

The scope remains essential. This result would offer no demonstrated route to a Bitcoin attack, establish neither P versus NP nor the difficulty of every practical instance, and provide no blanket verdict on the usefulness of optimisation. The wider argument rests on the particular limit the proof would establish.

We see real value in agents helping communities understand those limits. Scientific discovery can change which questions people pursue as well as the answers they obtain. Here the prospect is a better-founded account of computation, developed through a new contribution to a long human investigation. That would be a meaningful advance even though the result tells us why some ambitions must change.

Source note: we read the selected theorem and construction overview, followed the original approximation-hardness sources and enumerated our four-vertex example. We also read the relevant released reasoning summary where cited. Sources checked 8 October 2026. We haven't independently certified these manuscripts or run a Lean build.