OpenAI and Anthropic Both Say Their Models Refuted the Exponential Time Hypothesis on October 16. Anthropic Says No Person Is Known to Have Checked Its Lean Proof.
On Monday, October 26, 2026, OpenAI said an internal model had refuted the Exponential Time Hypothesis, one of the standard assumptions of theoretical computer science. It posted the preprint and a Lean formalization to its public math repository and announced a review process led by two of the people who proposed the hypothesis.
That evening, Anthropic posted its own refutation, credited to "Claude (Anthropic)." The commit landed at 8:07 p.m. Pacific, under six hours after OpenAI merged its update at 2:18 p.m. Both labs say their models found the core result on the same day: Friday, October 16.
That coincidence alone would be a story. So is one detail Anthropic put in its own appendix: the Lean proof "was written by AI models and reviewed by other instances of the same models; at the time of writing no person is known to have checked it."
What Is Being Claimed
3-SAT asks whether a logic formula over n true-or-false variables can be satisfied. Trying every assignment takes 2n steps. Decades of work shaved that down: both papers cite a deterministic record of about 1.328n, from a 2018 result by Liu. Every improvement kept the running time exponential.
The Exponential Time Hypothesis, proposed by Russell Impagliazzo and Ramamohan Paturi of UC San Diego with Francis Zane, says that is unavoidable: some fixed exponential rate is a hard floor. Researchers use it to show, conditionally, that problems in graph theory, computational biology, databases and geometry cannot be solved quickly. Anthropic's paper says a literature search by Claude found more than 800 papers that prove at least one result only under ETH or a hypothesis that implies it.
Both labs now claim a deterministic algorithm that counts the satisfying assignments in subexponential time, which would make ETH false. Counting is harder than deciding, so the claims are slightly stronger than what a refutation needs. Here is how the two releases compare.
| OpenAI | Anthropic | |
|---|---|---|
| Paper | The Exponential Time Hypothesis is False, by OpenAI | A 2o(n) Time Algorithm for 3-SAT, by Claude |
| Date on paper | October 17, revised October 25 | October 26 |
| Core result found | October 16; Lean check October 17 (per OpenAI) | October 16, 14M output tokens, no human input (per the paper) |
| Headline bound | 2O(n log log n / √log n), polynomial space | 2O(n log log n / √log n) for #3-SAT |
| Lean proof | Nearly 4,000 Lean files in its SubexponentialSAT folder (our count) | 1,050 Lean modules, built on Mathlib |
| Second kernel | nanoda switched off in its Comparator config | Checked by nanoda through Comparator, plus leanchecker |
| Human review | Working group led by Impagliazzo, Paturi and Ryan Williams | None named in the paper or README; "no person is known to have checked" the Lean |
The headline bounds match. That does not mean the proofs match. OpenAI's paper reduces the problem to counting common zeros of polynomial equations, and proves its sharper bounds by tensor contraction in an appendix. Anthropic's condensed description is built on contracting tensor networks. Its paper says that, "Independently and concurrently, an internal model at OpenAI claims to have proven a similar result."
What It Does Not Do
Nobody should expect faster SAT solvers. Anthropic's paper says that for 3-SAT formulas with five clauses per variable, its bound does not beat brute force until n is above 1010,000. Brute force is already impractical at 100 variables. In the paper's words, the result "says nothing about solving formulas in practice."
It also does not settle P versus NP. Subexponential is still far slower than polynomial. On cryptography, Williams told TechCrunch that he asked OpenAI science lead Dan Roberts whether any systems were affected. "And apparently, they checked, and they were reasonably confident that this didn't … imply any breaks."
What it does do, if it holds, is knock out a foundation. Anthropic notes that the refutation also refutes the Strong Exponential Time Hypothesis, though not the Orthogonal Vectors hypothesis, on which many lower bounds in fine-grained complexity rest. Williams told TechCrunch that "Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one's weight may vary." He added: "I don't think that OpenAI's algorithm could possibly be the best algorithm you can get."
Who Checks It
OpenAI's release notes say the working group asked for the materials to be made public immediately. In an open letter quoted by The Next Web, Impagliazzo, Paturi and Williams wrote: "Our involvement should not be taken as certification of the claim." Williams said the group signed no non-disclosure agreements and will not be paid. It asked OpenAI to release its raw data and fund a conference; according to both Williams and OpenAI, OpenAI agreed.
This is a turn for Williams. TechCrunch reports he called OpenAI's early-October dump of math papers a "DDOS attack on mathematicians." Now he is organizing the response. Having looked at the proof, he told TechCrunch there are "two or three alien-looking parts."
ETH was one of three results OpenAI announced Monday. It also claims Sogge's local smoothing conjecture in every dimension, which would settle the Kakeya conjecture, and an existence proof for four-dimensional quantum field theories including pure Yang-Mills. A physics group led by Nobel laureate David Gross chose not to release that material yet. OpenAI also points to the $5 million it has given the Simons Foundation for workshops on AI-produced results.
Anthropic's release came with less ceremony. Its README says a Hexagon link is "to appear," and neither the README nor the paper names an outside review group. TechCrunch reports that Anthropic mathematician Levent Alpöge suggested OpenAI was building on pre-existing work, hours before Anthropic released its own refutation. The README also says Claude Opus 5.5 at high effort can rederive a weaker form of the result from a condensed description a few sentences long.
Our Take
Two separate machine-checked proofs of the same statement, from two labs that had every reason to find a hole in the other, is stronger evidence than either alone. We now think ETH is more likely false than not. But Anthropic's appendix names the gap precisely: Lean can confirm the proofs, but "no machine can check" whether the formal statements say what the papers say. That part is a human job, and the outside review of it has only begun.
That is where review effort should go first. Anthropic kept its statement file short so a reader could check it. OpenAI's working group should read both labs' statement files before it reads either paper, and Anthropic should hand its proof to the same three people rather than leave it on GitHub with a link to appear. If two labs are going to publish rival proofs on the same evening, the field's scarcest resource is no longer discovery. It is the handful of unpaid experts who can say whether a theorem means what its title says.
The race framing is the least interesting part of this story, and the most likely to get worse. Next time, expect a lab to publish first and verify later. The working group model, with public data, no NDAs and a funded conference, is the right template. Every lab claiming a result of this size should be held to it.
Sources: OpenAI (October 26), OpenAI preprint, OpenAI Comparator config, Anthropic formal-math/eth, Anthropic paper, TechCrunch, The Next Web, OfficeChai.