OpenAI and Anthropic Both Say an AI Refuted the Exponential Time Hypothesis. Neither Claim Has Peer Review, and the Lean Files Do Not Prove the PDFs.
OpenAI posted on October 26 that an internal model found a disproof of the Exponential Time Hypothesis on October 16 and formalized it in Lean on October 17, with Impagliazzo, Paturi, and Williams shepherding the result. On October 27 Anthropic deposited a paper by Claude claiming a subexponential 3-SAT algorithm, found on October 16 with 14 million output tokens and no human input, by Anthropic's account. Anthropic's README says no machine checks that its Lean file says what the paper says; Anthropic's checker config enables a second proof kernel that OpenAI's leaves off. Neither claim is peer-reviewed, and neither is P equals NP. We read both posts, both repositories, and the Hexagon deposit.
By T.W. Ghost
Two frontier labs claim their models refuted the Exponential Time Hypothesis, and both say the discovery happened on October 16. OpenAI went first, posting on October 26, 2026 that an internal model found a natural-language disproof on October 16, Lean-formalized it on October 17, and released the writeup and Lean code under a collaboration led by Russell Impagliazzo, Ramamohan Paturi, and Ryan Williams, with OpenAI funding a conference on the result. Today, October 27, Anthropic deposited "A 2^o(n) Time Algorithm for 3-SAT," author "Claude (Anthropic)," on Hexagon as 2610.00577v1, with Lean under eth/ in its formal-math repository. Anthropic's provenance note says the core algorithm was found on October 16 by an internal Claude research model, in 14 million output tokens, with no human input, and acknowledges OpenAI's concurrent claim.
Neither claim is peer-reviewed. Both labs frame their artifacts that way, and the shepherds are reviewing, not endorsing. The more specific catch is what the Lean files do and do not establish. Anthropic's README says the result is "purely asymptotic and says nothing about solving formulas in practice," and that "no machine checks that this file says what the paper says." The checker configurations differ too: Anthropic's comparator.json sets enable_nanoda to true, turning on a second proof kernel; OpenAI's SubexponentialSAT.json sets it to false. We read OpenAI's post, both repositories' READMEs and configs, and the Hexagon abstract. Here is what held up.
Two Claims, Side by Side
| OpenAI | Anthropic | |
|---|---|---|
| Public date | October 26, 2026 | October 27, 2026 (Hexagon 2610.00577v1) |
| Claimed discovery | October 16, internal model, natural-language disproof | October 16, internal Claude research model, 14M output tokens, no human input (vendor) |
| Formalization | Lean, October 17; in openai/math | Lean under eth/ in anthropics/formal-math |
| Claim | ETH is false; deterministic subexponential #3-SAT counting | 2^o(n) algorithm for 3-SAT; deterministic subexponential #3-SAT counting |
| Human review | Impagliazzo, Paturi, Williams shepherding; conference funded by OpenAI | Not stated beyond the provenance note |
| Second proof kernel (nanoda) | Off (enable_nanoda: false) | On (enable_nanoda: true) |
| Lean checked against the paper | Not claimed | Explicitly not: "no machine checks that this file says what the paper says" |
| Peer review | None | None |
| Practical SAT speedup | Not claimed | Explicitly disclaimed |
The Lean is not the paper, and one lab says so in its own README. A Lean file proves the theorem the file states. Whether that theorem is the one in the PDF, with the same constants and exponent, is a separate question that a human has to answer. Anthropic writes that nothing automated answers it. A secondary analysis argues OpenAI's Lean statement is weaker than its manuscript's; we have not re-derived that and label it as what it is, a claim from outside both labs.
The second kernel is a real difference, and a small one. Running two independent proof checkers is a hedge against a bug in one. It does not close the Lean-versus-paper gap, which is the gap that matters.
Same discovery date is a story, not evidence. Two labs landing on October 16 is the kind of coincidence that will get written up as a race. It says nothing about whether either proof holds.
What This Is Not
It is not P equals NP, and neither lab says it is. Both claims live inside the Exponential Time Hypothesis and #3-SAT asymptotics. A disproof of ETH, if it stands, says 3-SAT can be solved in time that grows slower than any fixed exponential; it does not say it can be solved in polynomial time, and Anthropic's README goes further to say it does not make any real formula faster to solve. Press framings that reach for P equals NP are reaching past both vendors' own text.
We are also leaving out a rumor that attaches the result to an unreleased Anthropic model name. It exists only on X.
Verified vs Unconfirmed: The Scorecard
| Claim | Verdict |
|---|---|
| OpenAI post Oct 26; discovery Oct 16; Lean Oct 17; shepherds named; conference funded | Verified (OpenAI post) |
OpenAI preprint and Lean in openai/math; enable_nanoda false | Verified (repository) |
| Anthropic Hexagon deposit Oct 27; author "Claude (Anthropic)"; 2^o(n) 3-SAT | Verified (Hexagon) |
| Found Oct 16; 14M output tokens; no human input | Vendor (Anthropic provenance note) |
| Asymptotic only; Lean file not machine-checked against the paper | Verified (Anthropic README) |
Anthropic enable_nanoda true | Verified (repository config) |
| OpenAI's Lean theorem weaker than its manuscript | Secondary; not re-derived here |
| Peer review of either claim | None |
| "P equals NP" | Contradicted by both labs' own statements |
What To Do
Read the READMEs before the headlines, and quote the labs' own limits: asymptotic, unreviewed, Lean not matched to the PDF.
Wait for the shepherds. The complexity theorists OpenAI named are the first people whose verdict changes anything; until then, treat both artifacts as raw research output, which is how OpenAI itself describes them.
The frontier is elsewhere: whatever the proofs turn out to be, nothing here changes a benchmark score or a price. Our model comparison has the current standings side by side, and the week's other Anthropic research disclosure, five working exploit chains from an unreleased model, is the one with operational consequences.
Sources
- OpenAI: building scientific understanding with academic communities
- GitHub openai/math: The Exponential Time Hypothesis is False (preprint PDF)
- GitHub openai/math: SubexponentialSAT comparator config
- Hexagon: A 2^o(n) Time Algorithm for 3-SAT (2610.00577v1)
- GitHub anthropics/formal-math: eth/README.md
- GitHub anthropics/formal-math: eth/comparator.json
- SXZ: ETH refutation claims, Lean statements, and constants (secondary)
*Not sure how much weight an unreviewed AI proof should carry in your own evaluation of a lab? Take the free 2-minute quiz and get matched. Then read what the same labs disclosed about their models with real access: Anthropic's S-1 sandbox paragraph.*