Two internal AI systems at competing labs — one at OpenAI, one at Anthropic — independently produced proofs that the Exponential Time Hypothesis is false, publishing their results hours apart on October 26, and both tracing the core discovery to the same date: October 16, 2026. The coincidence is extraordinary. The consequences, if the proofs survive independent scrutiny, could force researchers to revisit more than 800 published papers that used ETH as a foundational assumption.

The Exponential Time Hypothesis, proposed in 1999 by Russell Impagliazzo and Ramamohan Paturi of UC San Diego and later formalized with Francis Zane in 2001, asserts that 3-SAT — the canonical Boolean satisfiability problem at the heart of NP-completeness — cannot be solved in subexponential time. In simpler terms: the most fundamental class of logic puzzles, the hypothesis said, fundamentally resists any algorithm faster than a brute-force exponential search. Researchers in graph theory, computational biology, database optimization, parameterized complexity, and cryptography spent a quarter century building on that claim, using ETH to rule out entire classes of faster algorithms without needing to solve P vs. NP itself.

Both AI-produced proofs do exactly what ETH said was impossible. Both are Lean 4-verified — checked by a machine proof assistant that certifies the argument's logical consistency step by step — and both are available on GitHub.

OpenAI's Claim: Three Results in Ten Days

OpenAI's announcement on October 26 covered three distinct results from an unreleased internal model. The most significant for complexity theory is a paper titled "The Exponential Time Hypothesis is False," which describes a deterministic algorithm — one with no randomness — that exactly counts the solutions of a k-CNF formula in time roughly 2^(n/(log n)^(1/2+o(1))) using only polynomial space. Because counting satisfying assignments is harder than merely deciding whether any exist, an algorithm that does the harder job also handles the easier one. The 3-SAT case directly refutes ETH.

The model, which OpenAI has not released, produced the natural-language disproof on October 16 and formalized the result in Lean the next day. The paper carries an October 17 date and an October 25 revision date. Both the write-up and the Lean code are publicly available in OpenAI's GitHub repository.

OpenAI's announcement also covered a proof of the local smoothing conjecture — proposed by Christopher Sogge in 1991 — in every dimension. Because of how the conjectures are related, that result simultaneously settles the Kakeya conjecture and Stein's restriction conjecture in all dimensions. Human mathematicians had previously established the Kakeya conjecture only in three dimensions, with that proof published by Hong Wang and Joshua Zahl in 2025. A third result — a rigorous existence proof for certain interacting quantum field theories in four dimensions, including quantum chromodynamics (QCD) and pure Yang-Mills theory — constitutes a claimed solution to one of the Clay Mathematics Institute's seven Millennium Prize Problems.

OpenAI said in September it would not claim the Millennium Prize for its earlier Navier-Stokes result, and has taken the same position here: academic credit for AI-produced results should go to the researchers who explain and verify the work, not to OpenAI.

ETH's Originators Will Now Examine the Claim

The review structure OpenAI organized for the ETH result is unusual in its transparency. A group led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego — two of the three researchers who proposed ETH a quarter century ago — alongside Ryan Williams of MIT will check and explain the result independently.

Williams announced his involvement on X (formerly Twitter), and all three published an open letter to the theoretical computer science community that was explicit about what their participation means and does not mean.

"Our involvement should not be taken as certification of the claim. A result of this significance requires careful, independent scrutiny," Impagliazzo, Paturi and Williams wrote.

Williams confirmed the group signed no non-disclosure agreements and would receive no payment. The group made two requests of OpenAI: release all raw data related to the ETH result, and fund a community conference to give the broader research community direct access to the work. OpenAI agreed to both requests. The company separately gave $5 million to Simons Foundation for workshops and conferences on AI-produced mathematics.

Paturi said his first reaction upon seeing the claimed result was surprise. Participating in the review, he said, was not optional: not taking part in the examination of a claim this important is unthinkable.

For the physics results, Nobel laureate David Gross is leading a separate review group, alongside Michael Douglas, Arthur Jaffe, Igor Klebanov and Nikita Nekrasov. That group took a more cautious approach than the complexity-theory panel: it declined to release AI-produced materials and will write up the physics work itself.

Claude Got There Too — on the Same Day

Hours after OpenAI's announcement went public, Anthropic published its own paper, titled "A 2^o(n) Time Algorithm for 3-SAT" and credited simply to "Claude (Anthropic)." The paper presents a deterministic algorithm for 3-SAT — and for the harder counting problem #3-SAT — in subexponential time, directly contradicting ETH by the same logic as OpenAI's result.

According to Anthropic researcher Levent Alpoge, who shared the result publicly, Claude's internal research model found the core discovery on October 16 using 14 million output tokens, with no human involvement in the discovery itself. Anthropic researchers then worked with Claude to improve how the result was written up.

Both labs apparently had no knowledge of what the other was doing. Anthropic's paper acknowledges OpenAI's concurrent result in a footnote, noting that an internal model at OpenAI claims to have proven a similar result. The two results arrived, by each company's own account, at the same algorithmic conclusion within what appears to have been the same window of days — a coincidence that, in the history of mathematics, has typically signaled that the tools needed to crack a problem had quietly become available to anyone working hard enough on it.

Mathematician Jelani Nelson, who reviewed Claude's proof independently, said both proofs appear to reach roughly the same asymptotic runtime bound — approximately exp(O(n / sqrt(log n))) — suggesting the two algorithms are closely related in technique even if they approached the problem independently.

Claude's disproof has one technical distinction from OpenAI's: it also disproves the SETH hypothesis, the Strong Exponential Time Hypothesis, a stricter form of ETH, because SETH logically implies ETH. Claude's paper additionally shows the result implies faster theoretical algorithms for a family of related problems, including Independent Set, Clique, Vertex Cover, and Dominating Set.

What Lean Verification Does — and Doesn't — Guarantee

Both proofs are formalized in Lean 4, which means a machine has verified that every logical step follows from the stated premises within the formal proof system. What Lean cannot guarantee — a distinction that has grown more important as AI-produced mathematics multiplies — is that the Lean formalization is a semantically faithful translation of the natural-language proof the AI actually wrote.

Anthropic's paper goes one step further than OpenAI's, adding an independent check: nanoda, a second proof kernel written in Rust by different developers, confirmed all declarations in Claude's Lean proof. Using a second kernel written in a different programming language by a different team catches classes of bugs that Lean's own checker might miss. Anthropic used the same two-kernel approach for its earlier Fermat's Last Theorem formalization.

Anthropic's paper also explicitly flags its own limitation in a footnote: the Lean development was written by AI and reviewed only by other instances of the same models, and as of its publication no person is known to have checked it by hand. The formal machinery has confirmed the logic is internally consistent. A human mathematician working through Claude's argument line by line has not been confirmed.

Researchers have documented AI formalization mismatches in Lean — cases where an AI-translated proof compiles correctly in Lean while failing to correspond to the original natural-language argument — meaning a passing Lean build can coexist with a flawed written proof. The review by Impagliazzo, Paturi and Williams is designed to supply the layer of understanding Lean cannot provide: does the proof strategy actually do what it claims, and does the Lean formalization correctly represent that strategy?

What a Subexponential SAT Algorithm Means — and What It Does Not

Both proofs are asymptotic results, and both papers are explicit about what that means in practice.

The ETH disproof establishes that an algorithm exists that solves 3-SAT in subexponential time — growing more slowly than any exponential function of the number of variables. That directly contradicts what ETH said was impossible. However, the algorithm does not produce meaningful speedup for any problem a computer could realistically solve. According to Anthropic's paper, the crossover point — the minimum problem size at which the algorithm actually beats simple brute-force search — requires roughly 10^10,000 variables. Brute-force search already becomes impractical around 100 variables. The result, as Anthropic puts it, says nothing about solving formulas in practice.

The disproof also does not bring the field any closer to resolving P vs. NP, computer science's most famous open question. P vs. NP asks whether polynomial-time algorithms exist for every NP problem — a much stronger demand than mere subexponentiality. ETH was always a strengthening of P ≠ NP, not equivalent to it. OpenAI's own president stated that P still probably does not equal NP.

What the disproof does do, if it survives review, is force the field to revisit a very large body of existing work. Anthropic's paper found that ETH lower bounds underpin 800 papers, spanning graph theory, database query optimization, parameterized complexity, and communication complexity. None of those papers' practical conclusions necessarily become wrong — but the formal justification many relied on would no longer stand, and researchers in each subfield would need to establish whether their specific results can be rebuilt on different foundations.

Who Gets the Credit — and Why That Question Has No Easy Answer

The simultaneous independent discovery creates a credit question that neither company can resolve on its own.

In their open letter to complexity theorists, Impagliazzo, Paturi and Williams acknowledged the structural problem directly: recognition in AI-era mathematics, they warned, may skew toward whoever publishes first or has access to the most powerful computational tools, while the painstaking work of checking a proof, explaining it to the community, and building on it receives less acknowledgment. That concern echoes one raised in the Leiden Declaration in June 2026, when a group of mathematicians endorsed by the International Mathematical Union called for new norms around AI attribution.

OpenAI's response to the credit question is to decline to claim it: the company has stated it will not seek academic recognition for the discoveries and that researchers who explain and verify the work should receive the credit. It contributed $5 million to the Simons Foundation to fund workshops and conferences where the community can engage directly with AI-produced results.

The Association for Human Mathematics, which formed after OpenAI's October 6 mathematical release and called on mathematicians to stop working with OpenAI over concerns about how AI-produced results were being attributed, has not yet publicly addressed whether the ETH disproof's structured review process — with named, independent, unpaid reviewers and no NDAs — addresses those concerns.

What Comes Next

The mathematical infrastructure for verifying results of this kind is being built in real time. Working with Anthropic researcher Levent Alpoge, mathematician Ethan Sussman of Northwestern University has set up a public GitHub repository specifically for independent checking of the ETH result.

The review panel of Impagliazzo, Paturi and Williams will be the field's first authoritative signal. A positive verdict from the scientists who proposed ETH would confirm that October 16, 2026 was a genuine turning point in computational complexity theory. A finding of error — in the natural-language proof, the Lean formalization, or the correspondence between them — would tell the community exactly where the breakdown is and leave the question open.

Until that verdict arrives, the ETH disproof and its simultaneous twin sit in an unusual epistemic position: machine-verified in a formal system, publicly available for anyone to inspect, acknowledged by the field's leading experts as something that requires careful, independent scrutiny, and potentially consequential enough that — in the words of those same experts — a correct proof would change an important part of theoretical computer science. Impagliazzo, Paturi and Williams stated precisely that in their open letter to researchers.

Frequently Asked Questions

What is the Exponential Time Hypothesis, and why does it matter whether it is true?

The Exponential Time Hypothesis (ETH) is a mathematical conjecture from 1999 stating that 3-SAT — the canonical "logic puzzle" at the center of NP-completeness — cannot be solved meaningfully faster than exponential time. More than 800 published research papers used ETH as a foundation to prove that specific problems in graph theory, computational biology, databases, and other fields are computationally hard and that known algorithms for those problems are essentially optimal. If ETH is false, those formal justifications need to be reconsidered, though it does not automatically mean the problems become easy to solve.

Does disproving ETH mean AI has solved P vs. NP?

No. P vs. NP asks whether there exist polynomial-time algorithms for every problem that can be verified in polynomial time. The ETH disproof establishes only that a subexponential algorithm exists for 3-SAT — a weaker claim. ETH was always a stronger statement than P ≠ NP, and disproving ETH says nothing about whether P equals NP. OpenAI's own president stated that P probably still does not equal NP. The disproof also does not produce any algorithm that would be practically faster for any realistic problem size.

If Lean has already verified both proofs, why is independent human review still needed?

Lean checks that the formal proof term is logically consistent within Lean's axiom system. It does not verify that the Lean formalization correctly captures the natural-language argument the AI produced. Researchers have documented cases where AI systems produced mismatched Lean formalizations — where a passing Lean build coexists with a flawed written argument — meaning a formally verified Lean proof does not guarantee that the natural-language reasoning is correct. The review by Impagliazzo, Paturi and Williams is designed to supply the layer of understanding Lean cannot provide: does the proof strategy actually do what it claims, and does the Lean formalization correctly represent that strategy?

When two AI systems produce the same discovery on the same day, who gets the credit?

No consensus exists yet, and that is precisely the structural problem the open letter by Impagliazzo, Paturi and Williams raised. Both OpenAI and Anthropic have waived claims to academic credit, directing recognition toward the researchers who verify and explain the work. But the credit question extends further: the community is still developing norms for how AI-produced results should be cited, whether the verifying researchers become the paper's authors, and how journals should treat machine-generated proofs. The Leiden Declaration and the Association for Human Mathematics have both pushed for explicit attribution standards. The ETH dual-discovery will likely accelerate that conversation.