Anthropic publishes a 3-SAT algorithm found by an internal Claude research model: its paper and Lean 4 proof claim to refute the Exponential Time Hypothesis

Background and pain points

The Exponential Time Hypothesis (ETH) is a standard assumption in complexity theory: it says 3-SAT cannot be solved in 2^o(n) time, and many fine-grained lower bounds rest on it. On Oct 26 OpenAI announced a model-produced refutation of ETH. On Oct 27 Anthropic published a separate result in the eth folder of its official anthropics/formal-math GitHub repo: the paper "A 2^o(n) Time Algorithm for 3-SAT", credited to Claude (Anthropic). Levent Alpoge (@__alpoge__), a mathematician whose X bio lists Anthropic, posted that an internal Claude research model found the core algorithm on Oct 16 with 14M output tokens and no human input, and that Anthropic researchers then worked with Claude to improve the presentation.

Architecture and mechanism

Per the repo README, a deterministic algorithm decides 3-SAT on n variables in 2^o(n) time, refuting ETH, and in fact solves the harder #3-SAT (counting satisfying assignments) in 2^O(n log log n / sqrt(log n)) time. The condensed idea in the README involves contracting tensor networks on complete graphs, splitting SWAP operators by their number of singlets into low-rank pieces, and merging rows or columns into balanced classes to shrink the exponent recursively. The README also says Claude Opus 5.5 at high effort can rederive, from that condensed description, that 3-SAT is decidable in O(2^(delta n)) time for every delta > 0, though not the paper's sharper bounds.

Verification

This is not a benchmark result; what matters is checkability. The Lean 4 formalization was written by AI models. MainResults.lean imports only Mathlib and states that ETH is false (ETHIsFalse) and the main theorem. The README says the proofs depend only on Lean's three standard axioms (propext, Classical.choice, Quot.sound), and the repo's CI uses Comparator to match the statements and re-checks the proofs with a second, independently written kernel, nanoda. The README also notes that no machine checks that the Lean statement says what the paper says, so readers must compare them. The result is purely asymptotic, does not help solve SAT instances in practice, and still awaits independent review.

Getting started

To check it yourself, install elan, enter the eth folder, and run lake exe cache get, lake build, and lake env lean scripts/PrintAxioms.lean. Anthropic says the build took about 8 minutes on 24 virtual CPUs with a peak process of about 7 GB. The folder is Apache 2.0, a research artifact that is not maintained and does not accept contributions. For developers, the bigger signal is that two leading labs are now pairing long autonomous model reasoning with Lean machine checking on frontier math.