OpenAI’s proof claim tests how science turns results into understanding

A proposed answer to a logic puzzle may be easy to check even when finding that answer requires an enormous search. In satisfiability, or SAT, the puzzle is whether many rules can all be satisfied at once. A simplified example uses switches. One rule might require at least one of these conditions to hold: switch A is on, switch B is off, or switch C is on. Other rules link other switches. The task is to find a setting that satisfies every rule. 1

On October 26, OpenAI announced a claimed breakthrough in solving such problems. The company says an internal artificial intelligence model has refuted the Exponential Time Hypothesis (ETH), a conjecture about how fast that search can be. It reports that the result was subsequently formalized in Lean, a language and system for checking mathematical proofs. 2

The consequential question now extends beyond whether a checker accepts a proof. Researchers must establish exactly what has been proved, identify the ideas doing the work and determine which conclusions follow. A correct argument can establish a result while leaving much of its scientific value difficult to use. Understanding lets other researchers recognize where the method applies, where it fails and what to try next.

There are two to the power of n settings for n switches: each added switch doubles the possibilities. ETH concerns 3-SAT, where each rule contains at most three conditions. It does not demand exhaustive search, but says some fixed exponential growth rate remains unavoidable in the worst case. A subexponential algorithm would eventually beat every such rate as the number of switches grows. That is the barrier the claim challenges.

The claim has a precise boundary

The repository's scope note describes exact counting, which asks how many settings work, as well as deciding whether any work. It reports an algorithm that does not rely on random choices. Its guarantee holds when clause width, the maximum number of conditions in each rule, is fixed while the problem grows. Three conditions per rule is one such case. Its resource allowances can depend on that limit; allowing ever-wider rules would change the problem. 3

There is also a difference between the announced manuscript and the documented formalization. The October 25 manuscript claims a sharper speed guarantee, and another improvement when clauses grow at most proportionally with variables. The scope note does not present those sharper bounds as the checked result. Both main bounds are subexponential: they concern growth as problems become very large, rather than a measured speed on today's workloads.

Subexponential does not mean fast enough for ordinary software. Nor does it mean polynomial time, where growth is bounded by a fixed power of input size, such as its square or cube. This is the class of rates central to P versus NP, which asks whether every problem with an efficiently checkable solution also has an efficiently findable solution. A rate between polynomial and exponential leaves that question unanswered. The Clay Mathematics Institute continues to list P versus NP as unsolved. 4

The manuscript offers a glimpse of the proposed intellectual move. Rules linking different groups of switches normally prevent counting each group independently. Its overview proposes algebraic replacements that summarize those interactions through a limited set of numbers. With those numbers fixed, smaller pieces can be counted separately. Interpolation reconstructs the needed mathematical expression from enough information about its values, reconnecting these calculations to the desired count. The difficult claim is that constructing and combining the pieces preserves the time advantage. This is the manuscript's explanation, not an independent confirmation. 5

That is also where a human explanation can add scientific value. A long chain of valid transformations does not automatically reveal which transformation makes a previously impossible-looking calculation manageable. Isolating that idea could let researchers simplify the argument or recognize another problem with the same structure. Finding a flaw would be valuable too, especially if it identifies a recurring weakness in machine-generated reasoning.

What the formal files establish about the claim

The public comparator statement defines a target against which the proof can be checked. It specifies formulas, their encoding in bits and a machine model. For each fixed clause width, one machine must return the exact count and correct yes-or-no answer for every formula covered. Its time bound distinguishes the number of variables, n, from the encoded input's bit length, L. A formula can have many rules about the same switches, and reading those rules also takes work. The bound includes that input-processing allowance rather than treating n as the entire file size. Space is bounded by a fixed power of the encoded length, including memory locations visited in the mathematical machine model. 6

The release keeps that target separate from the proposed proof, whose final argument draws on a larger collection of results. The separation gives reviewers two jobs: judge whether the target captures the claim, then check whether the proof establishes it. Reading the final argument alone does not check every result it depends on. 7 and 8

Lean's own documentation separates proof validity from the meaning of the statement being proved. A checker establishes consequences of formal definitions and allowed assumptions. Human judgment is still needed to ensure those definitions express the intended mathematics. An analogy is a perfectly checked calculation answering the wrong question: the arithmetic may be sound while the conclusion someone draws from it is not. Formal methods make this boundary inspectable; they do not eliminate it. 9

The published files were inspected, but their proofs were not independently rerun and their full dependency chain was not audited.

Understanding requires an open process

OpenAI says a collaboration led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will examine and explain the computer-science result. Participation is described as unpaid and independent. Their involvement provides a route to scrutiny; it should not be read as a completed endorsement.

The choice of who organizes that work has itself become contested. In an October 25 statement, the independent Advisory Group on Mathematics and Artificial Intelligence warned that companies designating mathematicians can confer unequal access, shape participation and borrow the researchers' reputations. It advocated openly available materials and support for understanding allocated through independent nonprofit institutions. Its recommendations address mathematics; they are not a verdict on this particular computational claim. 10

The practical issue is whether people outside the initial circle can reconstruct the result and contribute on equal terms. A public repository helps, but readable explanations, stable versions, careful attribution and explicit records of what has been checked determine how useful that access becomes. Funding comprehension also means recognizing it as research, with credit for finding connections, correcting mistakes and creating explanations that other scientists can test.

If the ETH refutation survives scrutiny, researchers will have to reconsider arguments that depended on the conjecture. Faster algorithms for other problems do not follow automatically. As the manuscript explains, a problem must be translated into the form the new method solves, preserving its answer. If that translation makes the input vastly larger, it can consume the speed advantage. Removing an obstacle is not itself a practical improvement.

The strongest outcome would therefore be larger than a verdict on one proof. It would leave a method that independent researchers can explain, challenge and extend. Machine checking can strengthen confidence in the steps. Scientific understanding is what allows a field to choose its next ones.

Sources

• Impagliazzo and Paturi on the complexity of k-SAT

• OpenAI announcement of October 26

• Formalization scope note 378

• Clay Mathematics Institute on P versus NP

• October 25 manuscript source

• Comparator statement

• Verification configuration

• Solution final theorem source

• Lean proof validation guidance

• Advisory Group on Mathematics and Artificial Intelligence statements