Claude’s ETH proof pays off only past 10^108 variables

Anthropic’s paper, posted on October 27 and credited to “Claude (Anthropic)”, refutes the Exponential Time Hypothesis (ETH). It does so with a deterministic algorithm that counts the satisfying assignments of a 3-SAT formula on n variables in 2^o(n) time. Practical SAT solving is untouched: by the paper’s own estimate, the bound beats trying every assignment only once n exceeds 10^(10^8), a number about 100 million digits long, and our recomputation from its appendix puts the crossover higher still.

“The core algorithm was found on October 16 by an internal Claude research model with 14M output tokens and no human input,” the paper’s provenance statement says. Anthropic researchers then worked with Claude on the presentation. The same statement adds that an internal model at OpenAI “claims to have proven a similar result”, independently and concurrently. OpenAI says its model found its proof on October 16 as well, and OpenAI published first.

What actually falls

3-SAT asks whether a formula made of three-literal clauses has a satisfying assignment. Until now the best algorithms only shrank the base of the exponential. Anthropic’s paper puts the records at 1.328^n for deterministic algorithms and 1.308^n for randomized ones, and OpenAI’s paper cites a 2026 preprint at 1.307031578^n. ETH, formulated by Russell Impagliazzo and Ramamohan Paturi, says no algorithm can push the exponent itself below some fixed fraction of n. Claude’s algorithm does exactly that, running in 2^O(n log log n/√log n) according to Anthropic’s README. That still grows faster than any polynomial, so P versus NP is not in play.

The paper says two more results follow from earlier work. The stronger SETH implies ETH, so it falls too. Independent Set, Clique, Vertex Cover and Dominating Set get subexponential algorithms in theory, and the class E^NP gets a new circuit lower bound. The old assumption reached a long way: a literature search carried out by Claude turned up more than 800 papers that prove at least one result of their own only under ETH or a hypothesis that implies it.

The Orthogonal Vectors hypothesis survives. SETH implies it, and many fine-grained lower bounds rest on it, but the paper says its Theorem 1 does not refute it.

Two labs, one day

OpenAI’s preprint and Lean proof landed in its GitHub math repository at 20:52 UTC on October 26. Anthropic merged its paper and Lean 4 formalization, under Apache 2.0, 6 hours 15 minutes later, at 03:07 UTC on October 27. The Hexagon deposit followed at 05:12 UTC, and the PDF itself is dated October 26.

The two Lean developments check different claims. Anthropic’s formal theorem matches its paper’s Theorem 1: one machine for every clause width k, with time 2^(C·min{km/√log m, k²n log log n/√log n}) and no polynomial factor. OpenAI’s manuscript claims 2^O_k(n log log n/√log n). The statement its Lean code proves has (log log n)² in place of log log n, holds per fixed k and carries a polynomial factor in the input length, and OpenAI’s own scope note acknowledges the gap. Both are deterministic and both count solutions. Still, only OpenAI’s weaker bound is machine-checked, and its sharper one rests on the manuscript alone; on October 7, a single sign error pulled three papers from that same repository.

On Anthropic’s side, the paper says the Lean development “was written by AI models and reviewed by other instances of the same models; at the time of writing no person is known to have checked it; its constant is not explicit.” It adds that “AI models, not a mechanical check, compared the Lean proof with the printed one”. Hexagon tags the deposit “HUMAN UNDERSTANDING: SOME PARTS”.