Member-only story
What Is the Exponential Time Hypothesis? ETH, 3-SAT, and the AI Proofs Explained
A plain-English guide to the claimed refutation, what it changes, and how independent reviewers will check the AI-generated proofs.
TL;DR — The Exponential Time Hypothesis (ETH) is a conjecture that Russell Impagliazzo and Ramamohan Paturi proposed in 1999. It says that 3-SAT, a basic logic puzzle about setting true-or-false switches so that every rule holds, cannot be solved much faster than by checking an exponential number of possible answers. For more than two decades researchers have used ETH to set lower limits on how fast hundreds of other problems can be solved, and Anthropic counts more than 800 papers that depend on it. On October 26, 2026, OpenAI and then Anthropic released papers saying their models had found a deterministic algorithm that solves 3-SAT in subexponential time. Each paper came with a Lean formalization, and both labs date the discovery to October 16. If the proofs hold, a large part of complexity theory has to be rebuilt, though I would argue very little changes in practice, because the speedup appears only at problem sizes far beyond anything a computer will ever handle, a point Anthropic makes in its own materials. P versus NP remains open, OpenAI says it is reasonably confident no cryptosystem…
