Anthropic’s Claude also refutes ETH

Your AI and this story

Key facts

• README (verbatim): ‘A deterministic algorithm solves 3-SAT on n variables in time 2^o(n), which refutes the Exponential Time Hypothesis (ETH). The algorithm in fact solves the harder problem #3-SAT, counting the satisfying assignments, in time 2^O(n log log n / √log n). The result is purely asymptotic and says nothing about solving formulas in practice. The result was discovered by an internal research Claude model. This folder holds the paper and its Lean 4 formalization, which was written by AI models.’
• Provenance (paper, verbatim): ‘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. Independently and concurrently, an internal model at OpenAI claims to have proven a similar result [Ope26].’
• Lean verification, as the README states it: MainResults.lean states ETHIsFalse and MainTheorem ‘on Mathlib’s Turing machines’ and imports only Mathlib. PrintAxioms should give ‘’MainResults.ethIsFalse’ depends on axioms: [propext, Classical.choice, Quot.sound]’ (the same for mainTheorem), ‘Lean’s three standard axioms’. Lean and Mathlib v4.33.1 are pinned; the build takes about 8 minutes on 24 vCPUs. CI also runs Comparator against Challenge.lean and re-checks with the independent nanoda kernel
• Caveat (README, verbatim): ‘Lean checks the proofs, but no machine checks that this file says what the paper says; the file is kept short so that a reader can check this.’ Appendix E of the paper prints the file and lists its differences from the printed statements; proof/PaperIndex.lean maps each numbered statement to its Lean counterpart
• Method (paper keywords: ‘exact algorithms, tensor networks, rank’): contraction of tensor networks on complete graphs K_K with λ bits per edge, a recursion e(9K¹⁶) ≤ 0.9·e(K) + O(1/K) obtained by writing swaps as I − 2·singlet and grouping by low-rank operators, then sparsification (Impagliazzo–Paturi–Zane) for the bound in n. The README gives a five-line ‘condensed form’ from which ‘Claude Opus 5.5 at high effort can rederive the refutation’ (only the 2^(δn) for every δ > 0 version)
• Scope stated by the paper: refutes ETH and SETH and gives O(2^(δn)) algorithms for every δ > 0 for Independent Set, Clique, Vertex Cover and Dominating Set, and that E^NP lacks linear-size circuits; it ‘does not refute the Orthogonal Vectors hypothesis’. A Claude literature search found ‘more than 800 papers’ with results proved only under ETH or a stronger hypothesis
• Practicality (paper): ‘for arbitrary 3-CNF formulas with m = 5n clauses, the bound we prove does not improve on the 2^n of exhaustive search unless n > 10^10 000’, and the bound in n alone needs far larger n; ‘our result says nothing about solving formulas in practice’
• Comparison with OpenAI’s paper (17/25 Oct, 67 pp.): both are deterministic #k-SAT algorithms with time 2^(n·log log n/√log n) up to constants (OpenAI: (n+m)^O_k(1)·2^(O_k(n log log n/√log n)), paper; its Lean covers (log log n)² in place of log log n). OpenAI’s route goes through ‘shared linear summaries’, low-degree replacement forms and counting common zeros of sparse polynomial systems; Anthropic’s goes through tensor-network contraction and rank bounds. OpenAI’s paper also claims Gap-ETH and NSETH; Anthropic’s says it does not reach Orthogonal Vectors. Anthropic’s Lean covers its sharper bound, according to its README