Anthropic's Disproof of the ETH

The page presents a claimed refutation of the Exponential Time Hypothesis, which holds that 3-SAT cannot be solved in subexponential time in the number of variables. Its central result is a deterministic algorithm that purportedly solves 3-SAT in 2^{o(n)} time, where n is the number of variables. The claim is stronger than merely deciding whether a formula is satisfiable: the algorithm reportedly solves #3-SAT, counting the number of satisfying assignments. If correct, this would overturn a foundational assumption used to establish lower bounds for many computational problems.

The provenance statement says an internal Anthropic Claude research model found the core algorithm on October 16 without human input, after generating 14 million output tokens. Anthropic researchers then worked with the model to improve the presentation, and the claimed proof was formalized in Lean 4. The page also says an internal OpenAI model independently and concurrently claimed a similar result. Its extensive bibliography spans SAT algorithms, counting complexity, tensor methods, algebra, and formal verification, but the supplied material contains no explanation of the algorithm’s construction or proof. Readers therefore see a remarkable headline claim and account of how it was produced, rather than enough technical detail to assess why the algorithm works.