Anthropic Releases Lean 4 Proof Claiming an Internal Claude Model Independently Refuted the Exponential Time Hypothesis on October 16
“The core algorithm was found on October 16 by an internal Claude research model with 14M output tokens and no human input. Anthropic researchers worked with Claude to improve the presentation, resulting in this paper.”
Context
Two rival frontier AI labs have now published independent Lean 4 proofs claiming to refute one of computer science's foundational complexity hypotheses within hours of each other, signaling that autonomous AI reasoning models are converging on decades old theoretical breakthroughs.
The Exponential Time Hypothesis conjectures that deterministic algorithms for the 3SAT boolean satisfiability problem require exponential time in the number of variables and serves as a cornerstone of fine grained complexity theory. Hours before Anthropic published its repository, OpenAI announced on October 26 that its own internal models had refuted the Exponential Time Hypothesis alongside breakthroughs in harmonic analysis and quantum field theory.
Deep dive
Just hours after OpenAI announced that its internal reasoning models had refuted the Exponential Time Hypothesis, mathematician Levent Alpoge surfaced an Anthropic GitHub repository containing an independent paper and complete Lean 4 formalization proving the exact same landmark complexity result. The paper, titled A 2^o(n) Time Algorithm for 3SAT and authored by Claude at Anthropic, states that the core algorithm was discovered on October 16 by an internal Claude research model using 14 million output tokens and zero human input, after which Anthropic researchers worked with Claude to refine the mathematical presentation.
According to the repository documentation and the paper abstract highlighted by Andrew Curran, Anthropic's deterministic algorithm actually solves the harder counting problem #3SAT, computing the exact number of satisfying assignments for an n variable formula in subexponential time 2^O(n log log n / sqrt(log n)). The proof reduces 3SAT to contracting tensor networks on a complete graph K_K with lambda bits per edge, placing nodes on a grid where rectangle diagonals form a swap operator decomposed into singlets so row rank times column rank stays bounded by 12^lambda.
Unlike traditional preprints that rely solely on human peer review, Anthropic pinned the entire proof to Lean v4.33.1 and Mathlib v4.33.1 on Turing machines, verifying both ETHIsFalse and MainTheorem using only Lean's three standard axioms and rechecking the proof with the independent Comparator and nanoda kernel. Anthropic also published a single paragraph condensed prompt from which Claude Opus 5.5 at high effort can independently rederive the core subexponential 3SAT decision bound, while noting that the asymptotic result does not affect practical SAT solvers.
What to expect next
Because Anthropic's proof compiles in roughly eight minutes on 24 virtual CPUs in Lean 4 and passes an independent nanoda kernel check, theoretical computer scientists can immediately focus on verifying the short Turing machine specification in MainResults.lean rather than auditing dozens of pages of prose for subtle logical gaps. The simultaneous discovery by both OpenAI and Anthropic within days of each other will force mathematics and theoretical computer science journals to establish new norms for simultaneous AI theorem attribution and machine checked publication.