Anthropic publishes Claude’s claimed refutation of the Exponential Time Hypothesis

Anthropic has published a paper crediting an internal Claude research model with an algorithm that, if correct, would refute the Exponential Time Hypothesis. The October 27, 2026 paper says the result was formalized in Lean 4. Its publication page also makes a striking disclosure: human understanding of the work covers only some parts.

A speed claim that also covers counting

The paper, titled A 2^{o(n)} Time Algorithm for 3-SAT, claims a deterministic algorithm for 3-SAT problems with n variables. Its central assertion is the running-time bound: 2^{o(n)}, or subexponential time. That bound concerns how the work required grows with the number of variables, rather than a reported speedup on a particular test.

The claimed algorithm also handles a counting task. According to the abstract, it solves #3-SAT by counting the number of satisfying assignments—the assignments that meet the problem’s conditions. The paper describes this as the harder problem: its claim extends to counting the solutions, not just determining whether a solution exists.

Claude found the algorithm; researchers helped present it

The provenance statement dates the discovery to October 16. It says the internal Claude research model found the core algorithm using 14 million output tokens and no human input. Anthropic researchers then worked with Claude to improve the presentation, resulting in the published paper. The account assigns different roles to the model and the researchers: autonomous discovery of the core algorithm, followed by collaboration on explaining it.

Anthropic also acknowledges parallel work in that statement, saying an internal OpenAI model independently and concurrently claims to have proved a similar result. The paper’s references include OpenAI’s preprint, The Exponential Time Hypothesis is false, dated October 26.