OpenAI, Anthropic Say Exponential Time Hypothesis Is False
OpenAI and Anthropic both say AI models refuted the Exponential Time Hypothesis, with Lean proofs. What each claimed, what Lean checked, and who is reviewing it.
Amara Singh is a seasoned technology journalist with a background in computer science from the Indian Institute of Technology. She has covered AI and machine learning trends across Asia and Silicon Valley for over a decade.
On October 26, 2026, OpenAI said an internal model had refuted the Exponential Time Hypothesis (ETH), one of the load-bearing assumptions of theoretical computer science. Within hours, Anthropic posted its own refutation, written by an internal Claude model. Both come with a machine-checked proof in the Lean theorem prover. Neither has yet been accepted by the research community.
If either holds up, it overturns an assumption that a quarter century of complexity research has leaned on. Here is what each lab actually claimed, what Lean did and did not check, and why the result changes theory long before it changes any software.
What the Exponential Time Hypothesis says
ETH was formulated by Russell Impagliazzo and Ramamohan Paturi of UC San Diego, with Francis Zane, around 1999. It is about 3-SAT: given a formula of true/false variables joined into clauses of three, is there an assignment that makes every clause true? Trying every assignment takes 2ⁿ steps for n variables. Cleverer algorithms do better, but every one found in 25 years has still been exponential.
ETH says that is unavoidable: some constant δ > 0 exists such that no algorithm solves 3-SAT in 2^(δn) time. Researchers then used it as a premise. "Assuming ETH, problem X needs at least this much time" became a standard way to prove lower bounds in graph theory, databases, computational geometry and computational biology. OpenAI's announcement puts the number of papers relying on it in the hundreds.
Refuting ETH means showing 3-SAT can be solved in subexponential time, 2^(o(n)), where the exponent grows more slowly than n. That is still far from polynomial time, so it does not settle P versus NP.
What OpenAI claimed
OpenAI's 66-page preprint, The Exponential Time Hypothesis is False, dated October 17 and revised October 25, gives a deterministic algorithm that does more than decide 3-SAT. It counts the satisfying assignments of any k-CNF formula, for every fixed k, using polynomial space. The company says the model found the disproof on October 16 and the result was formalized in Lean on October 17.
The paper's main bound is 2^(O(n·log log n / √log n)) for n variables. For sparse formulas, with clauses at most a constant multiple of n, it tightens to 2^(O(n / √log n)).
The review is unusual. OpenAI asked Impagliazzo and Paturi, the two people who proposed ETH, plus Ryan Williams of MIT, to lead an outside examination. At their request, OpenAI agreed to make all raw data public and to fund a conference on the result. The three signed no non-disclosure agreements and are unpaid. In an open letter they wrote that their involvement "should not be taken as certification of the claim."
Paturi told The Washington Times his first reaction was surprise, and that if it holds up it would be "a major advance in our understanding of the limits of computation."
What Anthropic claimed
Anthropic's version, A 2^o(n) Time Algorithm for 3-SAT, was committed to GitHub at 03:07 UTC on October 27, the evening of October 26 in California. Its README credits "an internal research Claude model" and lists Claude as the paper's author. It claims the same headline: a deterministic algorithm that counts 3-SAT solutions in 2^(O(n·log log n / √log n)) time.
Anthropic is blunter about practice. The README says the result "is purely asymptotic and says nothing about solving formulas in practice." It also publishes a short condensed hint and says Claude Opus 5.5 can re-derive the weaker statement, that 3-SAT runs in O(2^(δn)) for every δ > 0, from it.
TechCrunch reported that Anthropic mathematician Levent Alpöge had first suggested OpenAI built on pre-existing work, hours before Anthropic released its own refutation.
| OpenAI | Anthropic | |
|---|---|---|
| Released | Oct 26, 2026 | Oct 27, 2026 (03:07 UTC) |
| Credited to | An internal OpenAI model | An internal research Claude model |
| Problem solved | Count solutions of k-CNF, any fixed k ≥ 2 | Count solutions of k-CNF (3-SAT headline) |
| Paper's time bound | 2^(O(n·log log n/√log n)) | 2^(O(n·log log n/√log n)) |
| Bound proved in Lean | 2^(O(n·(log log n)²/√log n)), weaker | min of 2^(C·k·m/√lg m) and 2^(C·k²·n·lg lg n/√lg n) |
| Lean axioms | Not stated in the scope note | Lean's three standard axioms only |
| External review | Impagliazzo, Paturi, Williams | Not stated in the release |
Sources: OpenAI Lean scope note and preprint; Anthropic MainResults.lean and README. "lg" is log base 2; OpenAI uses natural log.
What Lean checked, and what it did not
Lean verifies that a formal statement follows from definitions and axioms. It does not verify that the formal statement says what the paper says. Both labs acknowledge this. Anthropic's README notes that "no machine checks" that its statement file matches the paper, and keeps that file short so a person can read it.
There is also a gap in OpenAI's release. Its scope note says the Lean proof establishes 2^(O(n·(log log n)²/√log n)). The paper claims the sharper 2^(O(n·log log n/√log n)). Both are subexponential, so either one refutes ETH if correct. But the bound that was machine-checked is weaker than the one in the paper's abstract. Anthropic's Lean statement covers the sharper form.
The finding: how far apart the three bounds really are
All of these bounds hide constants inside the O(·), and neither lab states them. To see the shape of each bound, we set every hidden constant to 1, took logs as each paper defines them (natural log for OpenAI), and asked: at what number of variables does each bound first beat the best known algorithms for 3-SAT? The comparison points come from the OpenAI paper's own related-work section: brute force at 2ⁿ, Liu's 2018 deterministic algorithm at 1.32793ⁿ, and the best randomized bound, a Jiang–Cai preprint at 1.30703ⁿ.
| Bound | Beats 2ⁿ | Beats 1.328ⁿ | Beats 1.307ⁿ |
|---|---|---|---|
| Sparse case | ~3 vars | ~400 vars | ~800 vars |
| Paper | Always | ~10⁶⁵ | ~10⁷⁹ |
| Lean-checked | ~10²³⁹⁰ | ~10⁴⁶⁷⁵⁰ | ~10⁵⁵⁶⁹⁷ |
Number of variables at which each OpenAI bound, with hidden constants set to 1, falls below brute force (2ⁿ), the best deterministic algorithm (1.328ⁿ) and the best randomized bound (1.307ⁿ).
The machine-checked bound only falls below plain brute force beyond roughly 10^2,390 variables. The observable universe has about 10^80 atoms. The paper's general bound passes the best deterministic algorithm at about 10^65 variables, and the sparse-case bound at about 400. Method: solve exponent(n)/n = log₂(c) for each bound and each comparison base c, with hidden constants set to 1; the constants are unknown and could move every figure by many orders of magnitude.
Source: Stanford Tech Review calculation from the time bounds in OpenAI's preprint and Lean scope note. Hidden constants set to 1, natural log. Illustrative of shape, not of real running times.
This matters for reading the claim, not for judging it. ETH is a statement about asymptotics, so a bound that only wins at astronomical sizes refutes it just as completely. What the numbers show is that the result is a theory result, and that the checked artifact and the headline claim are two different bounds.
What a refutation would change, and what it would not
Lower bounds. Every "assuming ETH" lower bound loses its premise. The conditional theorems stay true as stated; what disappears is the reason to believe the bound is the real limit. Impagliazzo, Paturi and Williams wrote that the reductions and techniques built on ETH "retain their value, even as some of their interpretations may change."
P versus NP. It is not settled. Subexponential is still superpolynomial. Williams told TechCrunch that "every computer scientist should probably put a little more weight on the plausibility of P = NP," and that he does not think OpenAI's algorithm "could possibly be the best algorithm you can get."
Cryptography. RSA and elliptic-curve security do not rest on ETH. Williams said one of his first questions to OpenAI was whether any cryptosystem was affected, and that OpenAI had checked and was "reasonably confident" none was broken.
SAT solvers. No change. Industrial SAT solvers handle millions of variables with heuristics that no worst-case bound describes.
Has ETH been "disproved" before?
Claimed refutations are not new. A 2021 preprint, The #ETH is False, #k-SAT is in Sub-Exponential Time, claimed the counting version and was never accepted. What is different now is two independent releases, from two labs, each with a Lean proof anyone can rebuild, and an examination led by the hypothesis's own authors. Williams told TechCrunch some parts of OpenAI's proof are routine but "two or three" look alien.
The pattern continues a month of AI-generated mathematics. OpenAI has released hundreds of AI proofs this autumn, and this site has covered the gap between what Lean verifies and what a paper claims and what Lean checked in Claude's Fermat proof. The ETH examination is the first in which the people whose conjecture is at stake are leading the review.
The verdict on whether the Exponential Time Hypothesis is false will come from that review, not from either lab. For now, the honest status is: claimed twice, machine-checked twice, and not yet understood by the people who will decide.
Cover image: AI-generated illustration.