OpenAI said on October 26, 2026 that its AI had refuted a longstanding assumption about how quickly computers can solve certain difficult problems. The claim concerns the Exponential Time Hypothesis, or ETH—a foundation for research into computing limits, with potential implications for the people designing tomorrow’s algorithms.
The company has released a written argument and formal proof materials. It says an external group led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams will examine the work. Its announcement describes an open examination, not a completed independent verdict.
If the claim holds up, researchers would need to reconsider an important basis for judging which computational speedups are out of reach. For businesses and everyday software users, however, a change in theoretical limits is not yet evidence of faster applications or lower bills.
What assumption is being challenged?
Start with a collection of yes-or-no choices, called Boolean variables. Each rule requires at least one of a few conditions to hold: a particular choice must be true, for example, or another must be false. The task is to find whether any assignment satisfies every rule. In 3-SAT, each rule involves at most three such conditions.
With n choices, there are 2ⁿ possible assignments. But ETH is not the claim that a computer must try every one. As Russell Impagliazzo’s tutorial explains, algorithms can beat exhaustive search while still taking exponential time. ETH says an exponential component remains unavoidable in the worst case for 3-SAT as the number of variables grows.
The proposed escape is a subexponential algorithm: one whose exponent grows more slowly than the number of variables, rather than simply at a smaller constant rate. This is a statement about how the work scales on increasingly large problems, not how many seconds a current computer takes.
Researchers use ETH to derive conditional limits for other computational problems. The implication of refuting it is subtle: an argument saying “if ETH is true, this task cannot be solved that quickly” need not contain a mathematical error. But its premise could no longer establish that limit. A faster algorithm for the other task would still need to be found.
What the released proof is said to cover
OpenAI’s formalization scope note describes an algorithm that counts exactly how many assignments satisfy a formula with a fixed limit on the number of conditions per rule, including the three-condition case. Counting also answers the yes-or-no question: a count of zero means no assignment works.
The running-time bound the note says is proved in Lean is weaker than the sharper bounds in the accompanying manuscript. The published scope still describes a subexponential result for the specified inputs. But that formalization does not certify every stronger estimate in the manuscript.
Lean is a proof assistant: it checks a precisely encoded mathematical statement under specified definitions and assumptions. The Comparator checker documentation explains how a successful check can establish agreement between a proof and its target statement. That is different from experts determining whether the formal statement captures the intended claim and what follows from it.
For background on those different kinds of verification, see RohitAI’s earlier account of OpenAI’s AI-generated mathematics. That article covers a separate August release, not validation of this ETH claim.
Why subexponential does not mean practical
This claim does not settle P versus NP, which Clay Mathematics Institute continues to list as unsolved. That question concerns whether every problem with efficiently checkable solutions also has a polynomial-time solving algorithm—one bounded by a fixed power of input size. A subexponential bound need not be polynomial.
A mathematical illustration shows the gap. Suppose a hypothetical method took 2^√n steps. At n = 10,000, that is 2¹⁰⁰, or about 1.27 × 10³⁰ steps. This growth is subexponential, yet eventually exceeds every fixed power of n. This is an illustrative calculation, not OpenAI’s runtime formula or a benchmark.
There is a second limit to the conclusion. The manuscript warns that its subexponential guarantee does not automatically carry over to general NP problems through arbitrary polynomial-time translations. Turning another problem into a Boolean formula can enlarge the input enough to consume the claimed advantage.
For actual software, the unresolved questions include the hidden constants, other factors in the running time, and the problem size at which an implementation could beat existing tools. An asymptotic bound—the growth rate as inputs become very large—does not answer those questions by itself.
What would justify changing plans?
The public repository provides research manuscripts and proof artifacts, not evidence of a commercial speedup. For algorithm researchers, the useful next step is to examine the exact result and identify which existing limits depend on ETH. That is a research task, not a reason to discard every assumption about computational difficulty.
For a team choosing software or setting a computing budget, a reasonable decision threshold is more concrete: a usable implementation, comparisons with established solvers on representative workloads, and documented time and memory requirements. Until that evidence exists, the claim is a reason to follow the research—not to promise a cheaper or faster service.