# OpenAI says a model refuted the Exponential Time Hypothesis, and the hypothesis's authors are now checking the proof

The claimed disproof passed a Lean formalization within a day, while Anthropic's separate report of 17 Claude-designed scorpion-toxin binders demonstrates binding but no neutralization.

- Published: 2026-11-01T06:20:01.798Z
- Canonical: https://polylog.news/ai/2026-11-01/openai-says-a-model-refuted-the-exponential-time-hypothesis
- Publisher: Polylog (AI desk)
- Section: tech
- Sources: [OpenAI](https://openai.com/index/building-scientific-understanding-with-academic-communities/), [Washington Times](https://www.washingtontimes.com/news/2026/oct/27/openai-says-model-refuted-exponential-time-hypothesis/), [StudyFinds](https://studyfinds.com/did-openai-disprove-exponential-time-hypothesis/), [Unite.AI](https://www.unite.ai/openai-says-its-models-produced-three-proofs-in-math-cs-and-physics/), [Wikipedia](https://en.wikipedia.org/wiki/OpenAI_bulk_release_of_mathematical_papers), [Anthropic Research](https://www.anthropic.com/research/claude-scorpion-toxin-binder-design), [Let's Data Science](https://letsdatascience.com/news/claude-designs-17-scorpion-toxin-binders-but-not-an-antiveno-64043ff9), [Interesting Engineering](https://interestingengineering.com/ai-robotics/claude-scorpion-toxin-protein-binders)

On October 26 OpenAI [said its internal reasoning models had produced three theoretical results](https://openai.com/index/building-scientific-understanding-with-academic-communities/) in mathematics, theoretical computer science and mathematical physics. The most consequential is a claimed refutation of the Exponential Time Hypothesis (ETH), the 1999 conjecture that 3-SAT, a satisfiability problem central to computational complexity theory, has no subexponential-time algorithm. According to [Washington Times reporting](https://www.washingtontimes.com/news/2026/oct/27/openai-says-model-refuted-exponential-time-hypothesis/), the paper gives a deterministic algorithm that counts all satisfying assignments in subexponential time. The model produced a natural-language disproof on October 16, and the result was formalized in the Lean proof-checking language on October 17. OpenAI also reported a natural-language proof of [Sogge's local smoothing conjecture in every spatial dimension of at least two](https://www.unite.ai/openai-says-its-models-produced-three-proofs-in-math-cs-and-physics/).

The verification group includes two of the hypothesis's originators, Russell Impagliazzo and Ramamohan Paturi of UC San Diego, along with Ryan Williams of MIT. Paturi said his first reaction was surprise. [StudyFinds notes](https://studyfinds.com/did-openai-disprove-exponential-time-hypothesis/) that until the reviewers report, the Lean check is the only independent test the result has passed. Reviewers still need to confirm that the Lean statement matches the classical conjecture. The caution has a recent basis. On October 6 OpenAI [released 722 manuscripts](https://en.wikipedia.org/wiki/OpenAI_bulk_release_of_mathematical_papers) claiming partial results on problems including the Riemann hypothesis, and mathematicians objected to their validity and exposition. OpenAI later withdrew three of them.

Anthropic's result is narrower and comes with experimental data. An [internal Claude research model worked largely autonomously for 64 hours](https://www.anthropic.com/research/claude-scorpion-toxin-binder-design) across 12 protein design tools. It generated 318,484 minibinder candidates and computationally screened 553,052 protein-toxin pairs against five neurotoxins from scorpions found in Mexico, Brazil, North Africa and the Middle East, according to [Interesting Engineering](https://interestingengineering.com/ai-robotics/claude-scorpion-toxin-protein-binders). Of 211 designs tested in the lab, 17 bound their targets, an 8% hit rate. Two binders against the toxin Cn2 reached single-digit nanomolar affinity, meaning they bound it tightly. Anthropic is releasing all 211 designs with their predicted structures and assay results. It [explicitly does not claim an antivenom](https://letsdatascience.com/news/claude-designs-17-scorpion-toxin-binders-but-not-an-antiveno-64043ff9) and ran no in-vitro or in-vivo neutralization tests.

Both reports come from the labs themselves, not from independent reproduction. The binder data can be checked now because Anthropic released the full set. The ETH claim cannot be settled until the named reviewers finish.

## What this means

If the refutation holds, the conditional lower bounds that fine-grained complexity theory has built on the Exponential Time Hypothesis lose their foundation, and OpenAI gains a claim to a research-level discovery that no benchmark score can provide. That claim arrives just as Anthropic's IPO is setting public valuations for the sector. Both labs gain fundraising and recruiting value from these announcements, which is why what each lab announces and what outside reviewers have verified need to be tracked as separate facts. The closest precedent is Vinay Deolalikar's 2010 manuscript claiming to resolve P versus NP, which outside reviewers found to contain errors within weeks. This claim differs in two ways: it has a machine-checked formalization, and named reviewers have publicly agreed to check it, both of which increase the chance the proof withstands scrutiny without settling whether it is correct. The more likely outcome within weeks to a few months is that the Impagliazzo, Paturi and Williams group reports either a mismatch between the Lean formalization and the standard hypothesis, or a confirmed algorithm. Whether the formal statement matches the standard Exponential Time Hypothesis is what will decide the outcome. A confirmed algorithm would turn AI-assisted mathematical discovery from a marketing claim into a demonstrated capability. On the binder side, the next milestone to watch is neutralization testing, and a failure there would show that a binding hit rate alone overstates progress toward a therapeutic.

## What to watch

- The written assessment from the UC San Diego and MIT reviewers on whether the Lean formalization matches the standard ETH. That question alone will decide whether the result stands.
- Whether an outside lab runs neutralization assays on Anthropic's released Cn2 binders. A positive result would turn a binding demonstration into therapeutic evidence.
- Further withdrawals from OpenAI's October 6 manuscript release. More retractions would lower the weight readers give to the new claims.