OpenAI and Anthropic claim to refute the Exponential Time Hypothesis

Felix Laurent 28 Oct 2026 6 min read

big tech

On Oct 26, 2026, OpenAI published a 67-page paper titled "The Exponential Time Hypothesis is false." Hours later, Anthropic posted a 49-page paper of its own, credited to "Claude," with the same conclusion. Both labs say an internal model found the core argument on Oct 16. Both released Lean formalizations, and neither paper has been peer reviewed.

We read both papers, the Lean documentation and the letter from the researchers who will review the claim. Here is what each lab states and what is still open.

What the Exponential Time Hypothesis says

The hypothesis concerns 3-SAT, the textbook hard problem in computer science. A formula has n true-or-false variables, and the task is to decide whether any setting satisfies it. Trying every setting takes about 2ⁿ steps.

What is 3-SAT? Picture a row of on/off switches and a list of rules such as “switch 1 on, or switch 4 off, or switch 7 on.” Each rule names at most three switches. The question is whether one setting obeys every rule at once. Checking a given setting is easy, but finding one can be very hard. Problems from scheduling to chip testing can be rewritten as 3-SAT.

Russell Impagliazzo and Ramamohan Paturi stated the Exponential Time Hypothesis, or ETH, in a 2001 paper. It says there is a fixed constant δ above zero such that no algorithm solves 3-SAT in 2^δn time. Since the 1980s, researchers have only shaved the constant. Anthropic's paper puts the prior records at 1.328ⁿ for deterministic algorithms and 1.308ⁿ for randomized ones.

Exponential vs subexponential, in plain numbers. With 2ⁿ, every extra variable doubles the work, so 100 variables already mean about 10³⁰ settings. Records like 1.328ⁿ are still exponential, just with a smaller base. Subexponential, written 2^o(n), means the exponent grows slower than any fixed share of n. ETH said that was impossible for 3-SAT.

ETH is a working assumption across the field. OpenAI says it has been used in hundreds of papers, from graph theory to computational biology and databases. Anthropic says a literature search by Claude found more than 800 papers with results that rest only on ETH or a stronger hypothesis. Both labs now say that assumption is false.

Exponential Time Hypothesis: 3-SAT running time exponent, brute force 2^n, prior records 1.328^n and 1.308^n, OpenAI and Anthropic claim 2^o(n)

What OpenAI claims

OpenAI's paper gives a deterministic algorithm that counts every satisfying assignment of a k-CNF formula, not only whether one exists. It runs in time 2^{O(n log log n / √log n)}, times a polynomial factor, and uses polynomial space. That exponent grows more slowly than any δn, which is what refuting ETH requires.

Deterministic, counting, polynomial space. A deterministic algorithm flips no random coins and gives the same answer every time. Counting means it reports how many settings work, which is harder than a yes or no. Polynomial space means memory stays modest, even when the running time is enormous.

According to OpenAI, its system found the natural-language disproof on Oct 16, and the result was formalized in Lean on Oct 17. The paper is dated Oct 17 and revised on Oct 25. The Lean proof covers a slightly weaker bound, with (log log n)² in place of log log n, the formalization notes say. OpenAI also derives faster algorithms for counting graph colorings and perfect matchings.

The paper adds its own caveat. A 2^o(n) bound does not carry over through general reductions, so it does not make every NP problem subexponential. The same day brought a second claim from a different lab.

What Anthropic claims

Anthropic's paper, "A 2^o(n) Time Algorithm for 3-SAT," also gives a deterministic algorithm that counts satisfying assignments. Its headline bound for k-CNF formulas has the same n log log n / √log n rate. The paper says the result refutes the Strong Exponential Time Hypothesis too, but not the Orthogonal Vectors hypothesis, which many fine-grained lower bounds rely on.

ETH, SETH and Orthogonal Vectors. SETH is a stronger cousin of ETH. It says that as rules get longer, the possible speedup over brute force shrinks toward nothing. Orthogonal Vectors is a separate assumption about comparing two lists of numbers. Many “this cannot be done faster” results rest on it, and it still stands.

The paper says the core algorithm came from an internal Claude research model on Oct 16, using 14 million output tokens and no human input. Anthropic researchers then worked with Claude on the presentation. The repository says Claude Opus 5.5 at high effort can rederive a weaker refutation from a condensed description of the idea.

What is Lean? Lean is a programming language for mathematical proofs, and a computer checks every step. If a proof passes, each step follows from the stated rules. Lean cannot tell whether the statement was translated correctly from the paper, so humans still need to read it.

The Lean 4 proof of the main results uses only Lean's standard axioms, and a second, independent kernel rechecks it. The repository is candid about the limit: "no machine checks that this file says what the paper says." The paper calls OpenAI's work independent and concurrent. Neither lab claims the result has any practical use.

Why solvers will not get faster

Anthropic spells out how far away the gain is. For typical 3-CNF formulas with five clauses per variable, its bound beats brute force only when n exceeds 10^10,000. The bound that holds for any formula needs n above 10¹⁰⁸. Brute force is already impractical at n = 100.

OpenAI writes that turning the theory into practical improvements "will require significant further research." Neither result settles P vs NP. Their value is conceptual, which makes careful checking the main task.

What is P vs NP? P covers problems computers can solve quickly. NP covers problems where a proposed answer can be checked quickly. Whether the two are the same is the biggest open question in computer science. Refuting ETH would make 3-SAT somewhat easier than believed, but still not quick.

Who will check the proofs

OpenAI asked three researchers to lead the review: Impagliazzo and Paturi of UC San Diego, and Ryan Williams of MIT. Impagliazzo and Paturi proposed ETH, with Francis Zane. Williams has refuted strong versions of ETH in earlier work. OpenAI says participants sign no NDAs, are unpaid and speak only for themselves.

In an open letter, the three write that their involvement "should not be taken as certification of the claim." They plan a shared repository for notes and corrections, a public discussion blog and a possible virtual meeting before the end of 2026. Their resource list includes Anthropic's refutation alongside OpenAI's. OpenAI has also agreed to fund a conference on what the result means for the field.

The letter also raises a broader question. Early access to AI results gives some researchers an advantage, and credit may go to whoever publishes first. The three ask how credit should also reward the work of checking, fixing and explaining results.

The rest of OpenAI's release

ETH was one of three results in OpenAI's announcement. In mathematics, OpenAI says its models proved Sogge's local smoothing conjecture in every dimension, which would also settle the Kakeya and Stein restriction conjectures. That proof was produced on Oct 18 and formalized in Lean the next day.

In physics, OpenAI claims an existence proof for quantum chromodynamics and pure Yang–Mills theory in four dimensions. A group led by Nobel laureate David Gross will review it and has withheld the AI-produced materials for now. R&D World notes that the Clay Millennium Prize problem also requires a mass gap proof, which the announcement does not cover. The Washington Times summed up the mood in its headline: "Experts are checking."

Kakeya and Yang–Mills in brief. The Kakeya conjecture asks how small a shape can be if it holds a needle pointing in every direction. Yang–Mills theory describes the forces that bind particles inside atomic nuclei. Proving it exists mathematically, with a mass gap, is a $1 million Clay Millennium Prize problem.

Is ETH really false?

Not yet established. The evidence is unusually strong for an unreviewed claim. Two labs reached the same bound, independently according to Anthropic, and both proofs pass Lean checks. Still, Lean confirms only the formal statements, and Anthropic itself notes that nobody has machine-checked whether those match the papers. That gap, and the definitions of machines and running time, is exactly what the Impagliazzo, Paturi and Williams group must examine. If the review holds, hundreds of conditional hardness results will need a new footing. Practical SAT solvers will not change either way.

OpenAI and Anthropic claim to refute the Exponential Time Hypothesis

What the Exponential Time Hypothesis says

What OpenAI claims

What Anthropic claims

Why solvers will not get faster

Who will check the proofs

The rest of OpenAI's release

Is ETH really false?

Sources

READ NEXT

Daily AI digest, October 28

Apple brings touch to the Mac: everything from Pro and Tell week

Nvidia's Nemotron 3.5 Transcribe folds a speech stack into one model