OpenAI Says AI Disproved the Exponential Time Hypothesis

Introduction

On October 26, 2026, OpenAI announced that an internal AI system had produced a disproof of the Exponential Time Hypothesis (ETH), a longstanding conjecture about how hard Boolean formula satisfiability is. According to OpenAI, the system found a natural-language disproof on October 16, 2026, and the result was formalized in Lean on October 17, 2026. OpenAI also published the writeup and the Lean proof on GitHub and asked an outside group, led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego and Ryan Williams of MIT, to verify and explain the result.

The same announcement included a local smoothing and Kakeya result in mathematics and a Yang-Mills and QCD existence result in physics. This article is about the ETH claim only, because it is the one where the release model, public AI output plus an external working group, is most visible. For background on OpenAI's earlier batch release, see our earlier article on the October 6 math repository.

One caveat frames everything below. The result is not yet peer-reviewed or community-verified. A Lean check means the formal proof compiles; it does not replace expert review, and the working group's job is exactly that review.

Feature Overview

What the ETH is. OpenAI describes the ETH as a longstanding conjecture about the computational complexity of Boolean formula satisfiability, a problem deeply related to P vs. NP. It has been used in "hundreds of papers" to derive conditional hardness results in graph theory, computational biology, databases and computational geometry. TechCrunch reports that Impagliazzo and Paturi first published the ETH in 1999.

What OpenAI claims. In OpenAI's words, "our system has recently proved that the ETH is false, a result that was subsequently verified in Lean." The refutation takes the form of an algorithm that beats exponential time. The stated bounds are sub-exponential, 2^o(n).

What the Lean formalization states. OpenAI's Lean scope note (378.md) is more specific than the headline:

The working group and its terms. The group asked that all raw data be made public for independent verification and that OpenAI commit to funding a conference on the implications. OpenAI agreed to both. OpenAI lists four principles for these collaborations: transparency (no nondisclosure agreements), no academic credit sought by OpenAI, recognition for the group's own writeups, and independence (participation is voluntary and unpaid, and members do not speak for OpenAI).

Three release strategies. OpenAI says its shepherds advised different approaches per field. For math, release the AI output. For computer science, form an external group and publish the AI output. For physics, defer to the group, which is holding off on release. OpenAI states it does not yet know which approach will work best.

A second, independent claim. On October 27, Anthropic published its own refutation in a GitHub folder titled "A 2^o(n) Time Algorithm for 3-SAT", a deterministic algorithm that also counts #3-SAT in 2^O(n log log n / sqrt(log n)). Its README says the result "is purely asymptotic and says nothing about solving formulas in practice," and that it was discovered by an internal research Claude model with the Lean formalization written by AI models. TechCrunch reports that Anthropic mathematician Levent Alpöge had suggested OpenAI was building on pre-existing work; the sources reviewed here do not settle that question.

Usability Analysis

For most readers, nothing changes in practice today. Anthropic's README is explicit that its result says nothing about solving formulas in practice, and OpenAI says that turning theoretical advances into practical improvements "will require significant further research."

For complexity researchers, the immediate value is inspectable material: the natural-language manuscript and the Lean proof are public, and the working group has opened an invitation for community examination. TechCrunch reports that Williams expects many papers that rely on the ETH to need revisiting if the claim holds up, and that he pushed for the conference for that reason.

Security teams will ask about cryptography. TechCrunch reports that Williams asked OpenAI science lead Dan Roberts whether any cryptosystems were affected, and that OpenAI said it had checked and was "reasonably confident" the result did not imply any breaks. That is OpenAI's statement relayed through a news report, not an independent audit, and nothing in the sources claims P = NP has been shown or that cryptography is broken.

Williams' own assessment is measured. He told TechCrunch that "some parts are, maybe you could say routine," but that there are "two or three alien-looking parts" that the whole community needs to work through. He also said, "I don't think that OpenAI's algorithm could possibly be the best algorithm you can get."

Pros and Cons

On the positive side, the release pairs an AI-produced result with machine-checkable Lean material, public raw data, named domain experts and a funded conference. The collaboration terms, including no nondisclosure agreements, are written down.

On the limiting side, verification is just beginning. OpenAI itself notes that choosing initial shepherds "shapes who gets involved first and creates asymmetry of information." The Lean statement covers a precisely scoped counting algorithm, and readers need to follow how that maps onto the ETH as the community states it. The group's first public step was an open letter asking for feedback, which signals an open process rather than a settled verdict.

Outlook

Three things to watch. First, the working group's written assessment; OpenAI says the members' conclusions are their own and that they do not speak on its behalf. Second, the conference OpenAI agreed to fund, which is meant to address implications for the field. Third, how the physics group's decision to hold back its materials compares with the computer science group's decision to publish immediately. OpenAI also points to a separate $5 million contribution to the Simons Foundation for workshops and conferences on AI-produced results.

The parallel Anthropic release gives reviewers a second set of artifacts to compare.

Conclusion

OpenAI's ETH claim is a significant assertion with real supporting material: a dated timeline, public manuscripts, a Lean formalization and a credible external group. It is still an assertion until that group and the wider community report back. Complexity theorists, formal-methods researchers and anyone following how AI-for-science results are released will find it worth tracking. Our rating of 4 reflects the quality of the disclosure process, not a verdict on the mathematics, which remains under review.

Editor's Verdict

OpenAI's ETH claim deserves close attention, with the verdict on the mathematics itself left to the working group.

The strongest case for paying attention: the release pairs a natural-language manuscript with a public Lean proof, so the formal statement can be inspected directly. That level of disclosure sets a useful precedent for AI-produced results. Reinforcing that, a named group of three complexity experts with stated independence provides a clear venue for scrutiny — practical value rather than just headline appeal. The broader signal worth registering is straightforward: the Lean check confirms that the formal proof compiles, but the working group's expert review is what will decide whether the community accepts the refutation. On the other side of the ledger, one constraint is real rather than a marketing footnote: the result is not yet peer-reviewed or community-verified, so the claim remains under examination. Any citation of the result should carry that caveat. Layered on top of that, the Lean statement covers a specifically scoped counting algorithm, and mapping it onto the ETH as the community states it takes expert reading.

For complexity theorists, formal-methods researchers and readers tracking how AI-produced scientific results are released, this is worth following closely as the working group reports.