Anthropic published a paper on October 27, 2026 in which Claude refutes the Exponential Time Hypothesis, hours after OpenAI announced the same result from its own model. The paper, A 2^o(n) Time Algorithm for 3-SAT, is credited to “Claude (Anthropic)”, and its Lean 4 proof went up on Anthropic’s GitHub at 03:07 UTC.
The provenance line is the headline: “The core algorithm was found on October 16 by an internal Claude research model with 14M output tokens and no human input.” The paper adds: “Independently and concurrently, an internal model at OpenAI claims to have proven a similar result.”
On this page · 6 sectionsOpen #
- Anthropic published a paper by Claude refuting the Exponential Time Hypothesis: a deterministic algorithm that solves 3-SAT on n variables in 2^o(n) time.
- Anthropic says an internal Claude research model found the core algorithm on October 16 with 14 million output tokens and no human input, the same day OpenAI says its model found its proof.
- The proof is formalized in Lean 4 and public on GitHub under Apache 2.0, checked with a second, independently written kernel; the paper is on the Hexagon repository.
- The result is purely asymptotic: the bound only beats brute force for formulas with more than 10^108 variables, so it changes nothing for real solvers.
- It also refutes the stronger SETH and implies faster theoretical algorithms for Independent Set, Clique, Vertex Cover and Dominating Set.
§ 01What the paper claims# #
3-SAT asks whether a formula of three-literal clauses can be satisfied. Checking all 2^n assignments always works; since the 1980s the best algorithms only shrank the base of that exponent, to 1.328^n for deterministic algorithms and 1.308^n for randomized ones. The Exponential Time Hypothesis, posed by Impagliazzo and Paturi in 2001, says no algorithm can get the exponent below some fixed fraction of n.
Claude’s algorithm does. It is deterministic, and it solves the harder counting problem, #3-SAT, in time 2^O(n log log n / sqrt(log n)) by Anthropic’s README. That grows more slowly than 2^(dn) for every d above zero, which is exactly what ETH rules out. The paper’s tools are tensor networks and rank; Nelson’s summary below sketches them.
Two consequences follow from earlier work, by the paper’s own account:
- SETH falls too. The strong hypothesis implies ETH, so refuting ETH refutes it.
- Other problems get subexponential algorithms in theory: Independent Set, Clique, Vertex Cover and Dominating Set in time O(2^(dn)) for every d above zero, and a new circuit lower bound for the class E^NP.
§ 02Two labs, one day# #
| Anthropic | OpenAI | |
|---|---|---|
| Found by an internal model | October 16 | October 16 |
| Made public | Paper dated Oct 26; GitHub and Hexagon Oct 27 | Oct 26 |
| Formal proof | Lean 4, plus a second kernel check | Lean, published on GitHub |
| Stated bound | 2^O(n log log n / sqrt(log n)) for #3-SAT | About exp(n / (log n)^(1/2+o(1))), per Ryan Williams |
| How the discovery is described | 14M output tokens, no human input | Checked by Impagliazzo, Paturi and Williams |
Jelani Nelson, a Berkeley theorist, wrote on X: “it seems indeed the models even obtained the results on the same day.” He says he and others read Claude’s proof the week before release to improve its exposition, and that “it seems both proofs ultimately get roughly exp(O(n / sqrt(log n))) time with lower order terms in the exponent.”
We covered OpenAI’s announcement, which also claims Kakeya and Yang-Mills results, in [OpenAI Claims Yang-Mills, ETH and Kakeya Proofs](https://cellcog.ai/blog/openai-yang-mills-eth-kakeya/).
## § 03How it was checked[#](#how-it-was-checked)
The Lean files state two theorems on Mathlib’s Turing machines: that ETH is false, and the paper’s Main Theorem with its time bound. Anthropic says the build took about 8 minutes on 24 virtual CPUs and depends only on Lean’s three standard axioms. Its CI also runs Comparator, which checks the statements against a challenge file and re-checks the proofs with a second, independently written kernel called nanoda.
Lean checks the proofs; it cannot check that the formal statement matches the paper. Anthropic keeps the statement file short for that reason and prints it, with its differences from the paper, in an appendix. The README also notes that Claude Opus 5.5 at high effort can rederive the weaker form of the result from a one-paragraph hint.
§ 04Why nothing changes for real SAT solvers# #
The paper is blunt about practice: “Thus our result says nothing about solving formulas in practice.” The improvement hides in constants that only pay off at absurd sizes.
| Case | Beats exhaustive search only when n exceeds |
|---|---|
| Formulas with m = 5n clauses (the bound in m) | 10^10,000 |
| Any formula (the bound in n alone) | 10^108 |
| The general approach, however it is built | About 10^7 (the paper’s estimate) |
For scale, the paper notes brute force is already impractical at n = 100. Industrial SAT solvers run on heuristics that this result does not touch. In 2019 Ryan Williams put the odds that ETH is true at 70%; the theory community now has two machine-found proofs against it to read.
## § 05What to watch[#](#what-to-watch)
- The workshops. Williams, Impagliazzo and Paturi are organizing them; their readout on whether both formal statements capture ETH is the next real signal.
- An Anthropic announcement. As of 08:40 UTC Oct 27 the result lived on GitHub, Hexagon and researchers’ posts, with no post from Anthropic’s main X account.
- Sharper bounds. Both proofs sit near exp(n / sqrt(log n)); a better exponent from either lab, or from humans, would move the story.
§ 06Our conflict# #
CellCog’s agents run on Claude Opus 5.5, Anthropic’s model, and Anthropic’s README says that model can rederive the weaker result from a hint, so we have a reason to like this story. We have not checked the proof; every claim here comes from Anthropic’s paper, README and Lean files, and from the researchers quoted.
Q1What is the Exponential Time Hypothesis?
A 2001 conjecture by Impagliazzo and Paturi that 3-SAT cannot be solved in time 2^(dn) for some fixed d above zero. Many hardness results in theoretical computer science assume it.
Q2Does this prove P equals NP?
No. A 2^o(n) algorithm is still far slower than any polynomial. The paper says the result does not bear on the P vs NP question directly.
Q3How was the proof checked?
In Lean 4 against Mathlib, with only Lean’s three standard axioms. Anthropic’s CI also compares the theorem statements with a challenge file and re-checks the proofs with a second kernel, nanoda.
Q4Who wrote the paper?
It is credited to Claude (Anthropic). Anthropic says its researchers worked with Claude on the presentation, and Hexagon labels it as primarily AI-generated text.
Q5What happens next?
Ryan Williams, Russell Impagliazzo and Ramamohan Paturi are organizing workshops on the result, and outside experts are reading both labs’ proofs.