A second frontier lab now says its AI has knocked down one of complexity theory's working assumptions. On October 27 Anthropic merged a folder into its public formal-math repository on GitHub containing a paper, credited to Claude, and a Lean 4 development that it says proves the Exponential Time Hypothesis false. The release came within hours of OpenAI publishing its own claimed refutation of the same conjecture, and the two efforts describe themselves as independent.
The Exponential Time Hypothesis, proposed by Russell Impagliazzo and Ramamohan Paturi in 1999, holds that 3-SAT, which asks if some assignment of true and false values makes a formula built from three-literal clauses true, needs time exponential in the number of variables for some fixed constant. Anthropic's paper describes a deterministic algorithm that goes further than deciding: it counts the satisfying assignments, running in time 2 to the power O(n log log n divided by the square root of log n). Because that exponent grows more slowly than any constant multiple of n, the claim implies 3-SAT can be solved in 2^o(n) time.
Anthropic's account of how the result arose is unusual. According to the provenance note on the paper's Hexagon listing, an internal Claude research model found the core algorithm on October 16, spending about 14 million output tokens with no human input, after which Anthropic researchers worked with the model on the write-up. The listing tags the paper as primarily AI-generated text. The repository README adds that a high-effort run of Claude Opus 5.5 can rebuild the decision version of the refutation from a short condensed hint printed there.
The formal side is designed to be checked by outsiders. A short file, MainResults.lean, states two theorems on Mathlib's Turing-machine model: that ETH is false and the paper's main counting bound. The README says both rest only on Lean's three standard axioms, that the project builds in roughly eight minutes on 24 virtual CPUs, and that the repository's continuous-integration check uses the Comparator tool to recheck the proofs with a second, separately written kernel called nanoda. The code is released under Apache 2.0.
Anthropic is explicit about what the machine check does not cover. Lean confirms the proofs follow from the stated definitions, but no software confirms that MainResults.lean expresses what the paper means, and an analysis by SXZ.io quotes the paper as saying no person is known to have checked the AI-written Lean code. The same analysis notes that the theorem only asserts that a constant exists, and that by the paper's own arithmetic the bound beats brute-force search only for formulas with more than 10^10,000 variables in the five-clauses-per-variable case.
The comparison with OpenAI's work is already drawing attention. SXZ.io reports that Anthropic's Lean statement covers the paper's full bound and states ETH's falsity directly, while OpenAI's formal theorem proves a looser exponent than the one in its paper; Anthropic's configuration also turns on the second kernel, which OpenAI's leaves off. TechCrunch, covering both releases, quoted MIT's Ryan Williams saying that if the claims hold, many papers that assume ETH will need revisiting, and that the community should weigh the possibility of P = NP a little more heavily.
Formal peer review has barely begun. Williams, Impagliazzo and Paturi are organizing the computer-science community's response to OpenAI's claim and have written that their involvement should not be read as certification; no comparable review of Anthropic's paper has been announced. The practical stakes are limited for now. Anthropic stresses that the bound is asymptotic only and offers no speedup for real-world formulas, so the significance lies in the theory and in what it suggests about AI systems producing checkable mathematics.