OpenAI says an internal AI system has disproved the Exponential Time Hypothesis (ETH), a conjecture that underpins many claims about which computing problems are too hard to solve quickly. If the result survives review, it would force researchers to revisit some of those limits. It would not establish that P equals NP or give us a practical shortcut for every difficult problem.
The company announced the claimed ETH refutation on October 26, 2026, alongside results in mathematics and quantum physics. Its ETH manuscript and Lean formalization are public. Independent examination is still underway.
ETH is a conjecture, not a fundamental law of computer science. And even a machine-checked proof needs people to check what its formal statement actually means. The published materials make that question unusually concrete.
What disproving the Exponential Time Hypothesis would mean
Imagine a puzzle with 100 yes-or-no switches. A brute-force search might try as many as 2100 combinations. Many computational problems contain the same combinatorial explosion: adding a few variables can multiply the search space.
ETH concerns 3-SAT, a problem involving Boolean formulas with up to three literals per clause. Roughly, it says no algorithm can solve every instance with n variables in subexponential time, written 2o(n). Researchers use that assumption to derive conditional limits for other problems. If ETH falls, those ETH-dependent conclusions need reconsideration. The underlying problems would not automatically become easy.
OpenAI’s October 25 manuscript claims a deterministic, subexponential-time algorithm that counts every satisfying assignment of a fixed-width Boolean formula while using polynomial space. Counting solutions also answers whether any solution exists. If the algorithm and its claimed bound are correct, applying it to 3-SAT would refute ETH.
The qualifier is subexponential. An algorithm can beat 2cn asymptotically and still be vastly slower than any useful program on real inputs. OpenAI has not demonstrated a practical replacement for industrial SAT solvers. A theoretical improvement in growth rate is not a benchmark showing that today’s workloads run faster.
Does OpenAI’s ETH claim mean P equals NP?
No. P versus NP asks whether problems whose solutions can be checked efficiently can also be solved in polynomial time. The proposed algorithm offers a weaker guarantee: subexponential time.
For example, 2√n is subexponential but grows faster than every fixed polynomial. Calling both kinds of algorithm “faster than brute force” hides an enormous difference in what they promise.
A correct ETH refutation would be a major theoretical result without settling P versus NP, automatically defeating modern encryption, or making hard scheduling and optimization tasks suddenly tractable. Those outcomes would require additional arguments. They do not follow from the claim OpenAI has published.
What the Lean formalization actually checks
Lean is a proof assistant that checks whether a formal proof follows from precisely stated definitions and accepted logical rules. That provides substantially stronger evidence than an AI confidently writing “therefore, proved.”
But Lean’s proof-validation guidance separates a valid proof from the meaning of its theorem statement. The formal theorem must capture the intended mathematical problem. Its axioms and imported dependencies also need scrutiny.
OpenAI’s ETH formalization covers exact counting for canonically encoded, fixed-width formulas. The stated runtime is a polynomial factor in input length multiplied by 2 raised to O(n(log log n)2/√log n). The development also bounds the tape space used by the machine by a polynomial in input length.
The October 25 manuscript gives a sharper exponent with one log log n factor, rather than its square. Both exponents are sublinear in n, so either would contradict ETH if the definitions and deductions hold. The public Lean scope note does not claim to verify the manuscript’s sharper running-time estimate.
Reviewers therefore need to establish whether the formal statement faithfully captures ordinary 3-SAT, whether the runtime and machine definitions express the claimed computational bound, and whether independent checkers can reproduce the proof without problematic assumptions. Checking the derivation and interpreting the definitions are separate jobs.
The published scope documentation and source statements have been inspected for this article. The Lean development has not been independently rebuilt or certified here.
Three AI proof claims at different verification stages
The geometry claim deserves attention on its own. OpenAI says a new auxiliary partial differential equation supplies local-smoothing estimates that lead to results about Kakeya sets, which contain a unit-length line segment in every direction.
The geometry formalization includes full Hausdorff dimension for Kakeya sets. Full dimension is not the same assertion as positive volume. Describing the result simply as a proof about how much space these sets occupy can blur the actual mathematical claim.
The physics announcement needs more restraint. OpenAI claims rigorous existence results for theories including quantum chromodynamics, but the outside group led by David Gross has chosen to prepare its own presentation before releasing the materials. Readers cannot yet examine the physics artifacts as they can the public ETH materials.
The Yang–Mills Millennium Prize problem requires existence and a mass gap. OpenAI has not claimed to settle that full problem. An existence result alone would leave the mass-gap requirement unresolved.
Who is checking OpenAI’s ETH result?
OpenAI says its model produced the ETH argument on October 16 and formalized it in Lean on October 17. It obtained the local-smoothing argument on October 18 and formalized that on October 19. The October 26 announcement set out how the public review would proceed.
Russell Impagliazzo and Ramamohan Paturi, who helped originate ETH, and MIT’s Ryan Williams are organizing the examination of the computer-science claim.
Their involvement is not an endorsement. The group requested public access to the raw materials and freedom to scrutinize them without nondisclosure agreements or compensation. A reviewer agreeing to examine a proof has not thereby certified it.
On October 27, Anthropic published a separate Claude-generated ETH refutation claim, describing a different approach based on tensor networks and its own Lean checking procedure.
Two public claims give specialists more to compare. They do not amount to two independently accepted theorems. Each argument still needs examination on its own terms.
What would establish that ETH has fallen?
▪ If the proof survives scrutiny, ETH-dependent research will need its assumptions revisited, and AI-assisted theorem discovery will have passed an extraordinary test.
▪ If it fails, the failure could expose a gap between a polished formal statement and the mathematical problem it was supposed to settle. The location of that gap would help explain what the machine checking did and did not establish.
As of October 27, 2026, OpenAI has published a claimed subexponential algorithm and a corresponding Lean formalization. Independent mathematical acceptance remains pending.
Watch for reproducible checks of the precise theorem, human explanations of the algorithm, and explicit agreement about its consequences. A famous conjecture falls when the argument holds up. The announcement starts that examination.
Explore more from Popular AI:
Start here | Local AI | Builds & gear | Autonomy & policy | Fixes & guides | Popular AI podcast
Would you trust an AI-generated mathematical proof once it's formally verified, or would you still wait for independent experts? How much confidence should we place in AI-driven scientific breakthroughs?