Anthropic releases Claude ETH refutation claim and proof code

Anthropic released a paper and Lean proofs on October 27 claiming an internal Claude research model refuted ETH, the Exponential Time Hypothesis. The guide reports checks using only Lean’s three standard axioms.

The paper describes an asymptotic result, with no practical speedup or P-versus-NP resolution. Its appendix says no human was known to have checked the development when it was written.

The October 26 manuscript credits an internal Claude model with finding the algorithm on October 16, using 14 million output tokens without human input. Anthropic researchers then helped improve the presentation.

3-SAT asks whether true-or-false values can satisfy every clause, each containing at most three literals. ETH posits an exponential-time lower bound as variable count grows. The formal file distinguishes existence from counting assignments.

The algorithm represents clauses as nodes and shared variables as connections, restructuring sums into smaller tensor-network computations. It uses cancellations between terms to count assignments.

The formal statement measures time in steps of a deterministic Turing machine with finite alphabets. Its generalized counting theorem covers formulas without repeated clauses, with every variable present, at least four variables and at least two clauses. These conditions are explicit in the statement being checked.

Matching the checked statement to the paper

An index maps the paper’s numbered statements to Lean counterparts and checks that those declarations exist. It distinguishes the paper’s wording from the actual formal statement, so readers can trace a claim into code.

The index records differences between the written and formal arguments. Alternating two algorithms, for example, costs a constant factor in the paper but a constant power with input length added in the formal development. It also documents differences in computational steps and proof routes. Some intermediate results use decision statements; counting is proved separately.

Comparator checks whether a submitted proof establishes the target statement, uses only permitted axioms and is accepted by the Lean kernel. Its documentation also offers an additional, independently implemented kernel. This separates checking the submitted proof from simply trusting a report that a build succeeded.

Those guarantees have conditions: the target statement and its imported files must be trustworthy, execution isolation must work, and the relevant proof kernel must be correct. Under those assumptions, the tool promises agreement with the designated formal claim and acceptance by the checker.

OpenAI had announced its own ETH claim on October 26, saying it obtained a written disproof on October 16 and formalized it the following day. Its separate external examination is led by Russell Impagliazzo, Ramamohan Paturi and Ryan Williams. OpenAI describes participation as voluntary, unpaid and independent. Its rules allow participants to discuss intermediate findings publicly without nondisclosure agreements. OpenAI lists graph theory, computational biology, databases and computational geometry among fields using ETH-based hardness results.

Anthropic labels the release an unmaintained research artifact closed to contributions. Its guide leaves readers to judge whether the formal statement expresses the paper’s intended claim.