Anthropic Claims Its AI Also Disproved the Exponential Time Hypothesis, and the Field Is Calling It a 'Giant Bomb'

OpenAI's October 26 announcement that an internal model had refuted the Exponential Time Hypothesis now has a sequel. According to WIRED reporting published this week, Anthropic says its AI systems have independently produced a disproof of the same 27-year-old conjecture, and both companies have posted their proofs on GitHub in natural-language form alongside Lean formalizations — the machine-checkable proof format that has become the de facto standard for validating AI-generated mathematics.

The stakes are unusually high for a single theoretical claim. The Exponential Time Hypothesis, proposed in 1999 by Russell Impagliazzo, Ramamohan Paturi and Francis Zane, asserts that 3-SAT cannot be solved in subexponential time. Hundreds of papers across graph theory, computational biology, database systems and computational geometry rely on it as a load-bearing assumption to derive conditional hardness results. If it genuinely falls, a large body of published theory needs to be re-derived under different assumptions.

OpenAI's version of the claim is the more documented one. The company says its model produced a natural-language refutation on October 16 and a Lean formalization the following day, both now public. The 67-page paper, credited only to OpenAI, describes a deterministic algorithm that exactly counts satisfying assignments of any k-CNF formula using polynomial space, with running time around 2^(n/√log n) — still superpolynomial, but growing more slowly than the exponential bounds ETH rules out. OpenAI also says the same algorithm refutes the Strong Exponential Time Hypothesis and two related variants. Impagliazzo and Paturi at UC San Diego, along with Ryan Williams at MIT, agreed to shepherd the result, but they signed an open letter stressing that their involvement is not an endorsement, that they signed no NDAs, and that the output should be treated as raw research data rather than a finished scientific result.

Anthropic's parallel claim is newer and thinner in public detail: WIRED reports the company also posted a natural-language proof and a Lean formalization to GitHub, with verification still pending. Neither company's result has been independently confirmed. And Lean's guarantee is narrower than it sounds — it checks that a proof is correct with respect to the definitions written into it, not that those definitions capture the intended mathematical statement. In OpenAI's case, the bound actually verified in Lean is slightly weaker than the paper's headline claim, though still subexponential.

The academic reaction has swung between exhilaration and dread. Daniel Lokshtanov, a professor at UC Santa Barbara, estimates that around 50 of his published papers could become irrelevant or need revisiting if the claims hold, and he described the moment as "a giant bomb dropped into the middle of the field — it's really cool and terrible at the same time." Thore Husfeldt of the IT University of Copenhagen called the ETH work "fantastic" while noting the pace is "psychologically taxing for many people," adding that "every week, or every second week, the results announced by AI just annihilate the ongoing research projects of many people." Peter Jonsson of Linköping University took the long view: "I don't care if it's a human-written proof, or it's written by AI, or if an alien transmitted this proof to us. If it's true, then we must simply use it in the future."

The volume is escalating as fast as the ambition. WIRED notes OpenAI recently dumped 722 manuscripts covering 400 problems on GitHub. On the Cheeky Pint podcast, Sam Altman defended the blitz — "Humanity deserves fundamental knowledge, and we should not be sitting on a major fundamental science discovery" — while conceding the quest for mathematical challenges "got out of control" at times, and confirming more results remain unpublished: "We do. Of course." One claimed physics result, an existence proof touching quantum chromodynamics and the completed Standard Model, remains unreleased at the reviewers' request, with a group led by Nobel laureate David Gross checking it.

Researchers are quick to note that none of this breaks cryptography — the hardness assumptions underpinning encryption are different from ETH, and no practical speedup is on offer. The real significance is procedural. AI labs are now claiming results at the frontier of original mathematical discovery faster than the community can verify them, and the shepherd model — named experts who publicly referee rather than certify — is the emerging answer. The bottleneck in AI-accelerated science is no longer generating conjectures or even proofs. It is trust.