OpenAI says its AI disproved the Exponential Time Hypothesis, and two of the rule's authors will check it

For 27 years, computer scientists have leaned on a simple-sounding bet: some puzzles will always take exponentially growing time, however clever the method. On 26 October, OpenAI said one of its unreleased AI models had found a way around that bet. For now, the Exponential Time Hypothesis OpenAI says it has broken is being tested by some of the people who first wrote it down.

Russell Impagliazzo and Ramamohan Paturi of UC San Diego were part of the group that proposed the hypothesis in 1999. With Ryan Williams of MIT, they will lead an open check of the proof. None of it has been through peer review yet.

The Exponential Time Hypothesis, in plain words

Picture a logic puzzle with a long list of yes-or-no switches and rules about which switches can be on together. Computer scientists call it 3-SAT. Every switch you add can double the number of combinations to try.

The Exponential Time Hypothesis (ETH) says no method can escape that pattern for this puzzle. Clever methods can slow the growth, but the work still grows exponentially as switches are added. OpenAI says researchers have relied on this idea in hundreds of papers, to show that problems in graph theory, computational biology and databases are hard to speed up.

What OpenAI says its model found

OpenAI’s paper, signed simply “OpenAI” and dated 17 October (revised 25 October), describes a method that exactly counts the solutions of such puzzles. It says the method runs in “subexponential” time, meaning the work grows more slowly than ETH allows, with modest memory. Counting the solutions also tells you whether any exist, so the 3-SAT case would make ETH false.

According to OpenAI, the model found the argument on 16 October, and the company checked it the next day in Lean, a computer language that verifies proofs step by step. The paper and the Lean files are public on GitHub.

OpenAI made two other claims. One is a maths proof that would also settle the Kakeya conjecture, a long-open question about shapes. The other, not yet public, is a physics result on quantum chromodynamics, the theory of the strong force inside atomic nuclei. A group led by Nobel laureate David Gross will guide that one.

Who is checking, and on what terms

Williams wrote on Bluesky that the three experts “signed no NDAs and will receive no compensation,” so they can share findings as they go. They asked OpenAI to release all its raw data on the claim and to fund a conference for the research community. He says OpenAI agreed to both.

Their open letter is careful: “Our involvement should not be taken as certification of the claim.” A Lean check helps, but it only proves what was written down. Experts still need to confirm that the statement checked is the one that matters.

According to The Verge, OpenAI’s own maths advisers had just recommended that AI companies not give chosen experts first access to results. OpenAI says it knows that approach has trade-offs.

If the Exponential Time Hypothesis falls, what changes

Nothing changes on your phone today. Does P equal NP? This would not answer that famous question. OpenAI’s paper itself says the result does not mean every hard problem in that wider family, called NP, can now be solved this quickly. Standard references on ETH make the same point: the hypothesis failing would say nothing, on its own, about P versus NP.

Many “this cannot be done faster” results were built on ETH. If the Exponential Time Hypothesis is disproved, each of those needs a fresh look. In practice, a theoretical speed-up like this usually takes years to reach everyday software, if it ever does.

Why the checking matters more than the headline

There is real good here. OpenAI has published the paper and the machine-checked proof, and it agreed to the checkers’ requests. That is a meaningful step on from its 6 October release of hundreds of manuscripts, which its own log shows included three papers later withdrawn over a sign error.

The caution is just as real. This is one company’s claim about its own model, and an OpenAI math proof is not settled science until others can rebuild and explain it. On balance, the bigger story is how science checks AI work, whatever happens to the Exponential Time Hypothesis OpenAI targeted. As with Google’s Willow quantum chip result, the test that counts is independent. And as the gap between AI promises and proven payoff reminds us, a claim is where the work starts.

Watch for the working group’s first notes and the promised conference. If the rule’s own authors end up explaining why it was wrong, few answers could be more convincing.