OpenAI says its model refuted the Exponential Time Hypothesis. The proof has not yet been independently checked

In brief

On 26 October 2026, OpenAI said that one of its internal models had proved the Exponential Time Hypothesis (ETH) false. ETH is a widely used assumption in theoretical computer science. OpenAI published the model's write-up and a Lean formalisation on GitHub.

The result has not been peer-reviewed. A group led by Russell Impagliazzo and Ramamohan Paturi of UC San Diego and Ryan Williams of MIT is examining it. Impagliazzo and Paturi first proposed ETH, with Francis Zane.

What ETH says, plainly

Some logic puzzles ask whether there is any way to set a list of true/false switches so that every rule is satisfied. The best-known version is called 3-SAT. Trying every combination doubles the work each time a switch is added. ETH says that shortcuts may help, but the work still has to grow exponentially as puzzles get larger.

Hundreds of papers assume ETH is true to show that problems in areas such as graph theory, databases and computational biology cannot be solved quickly. If ETH is false, those results lose their foundation. The problems do not automatically become easy, though.

What OpenAI claims

The preprint, which its title page dates 17 October and revised on 25 October, describes a deterministic algorithm that counts every satisfying assignment of a formula. Its running time grows more slowly than exponentially. OpenAI says the model found the disproof on 16 October and that the proof was formalised in Lean on 17 October.

Three caveats apply:

• No peer review yet. The reviewing group has said its involvement "should not be taken as certification of the claim", as quoted by The Next Web.
• The Lean check is narrower than the paper. OpenAI's own Lean notes say the machine-checked time bound is weaker than the main theorem in the 25 October manuscript, which "gives the sharper time bound".
• No practical speed-up has been shown. OpenAI's 26 October announcement says turning theoretical advances into practical improvements "will require significant further research".

New Scientist quotes Leslie Goldberg of the University of Oxford as saying the result has no direct impact on the P versus NP question.

Anthropic's own claimed refutation, which Anthropic says was discovered by an internal Claude model, is published on Anthropic's GitHub in its formal-math repository. It says the result "says nothing about solving formulas in practice".

Why it matters

The practical effect on IT is close to zero for now. The bigger signal is that AI labs are now producing claimed results in areas where the main checks are formal verification and expert scrutiny. Lean confirms that a proof is valid for the statement it was given. It does not confirm that the statement means what the paper says. That distinction will matter whenever someone presents an AI system's output as "verified".

Sources and scope

Sources: OpenAI's 26 October announcement; the preprint and Lean scope notes in openai/math; New Scientist for expert reaction; The Next Web for the reviewers' quote; and Anthropic's claimed refutation, published on Anthropic's GitHub. All were checked on 28 October 2026. Both proofs are unverified claims. The "Why it matters" section is ByteNib editorial analysis. This article was researched and drafted with AI assistance, including Anthropic's Claude, and edited under ByteNib's editorial standards. Anthropic, whose Claude helps draft ByteNib content, makes a competing claim covered in this article, and its claims are attributed to it throughout.

Drafted with AI assistance and reviewed by the editor before publication.

Continue exploring: AI & Machine Learning analysis, the related implementation tutorial, and the structured learning path.