OpenAI Says Its Models Have Toppled a 30-Year-Old Speed Limit for Computation

A Proof Checker Becomes the Measuring Instrument

For three decades, the exponential time hypothesis lived where most foundational claims live: in the space between what anyone could prove and what everyone assumed. It was a ceiling drawn by argument, not by observation. OpenAI now says its models have produced an algorithm that breaks that ceiling — and that the result has been run through Lean, a piece of software that mechanically checks whether a mathematical proof actually holds together. It is a claim a machine can audit, line by line, until only two questions remain: does the proof pass, and does the thing it proves mean what its authors say it means?

The hypothesis itself is simple enough to hold in one hand. Take a logical puzzle with many parts, each of which can be true or false. The brute-force route is to try every combination. The exponential time hypothesis, proposed nearly 30 years ago, says that shortcuts may exist, but the work required still has to grow exponentially as the puzzle grows. [1] It is a statement about a floor under the cost of certain problems — not a guess about one clever trick, but a proposed law about the shape of difficulty itself.

Stefan Szeider at TU Wien in Austria has examined what OpenAI has released. He expects the result to withstand scrutiny. But he flags the gap that formal verification cannot close on its own: researchers still need to confirm that the formally proven statement means what its authors claim it means. A proof checker confirms the chain of inference. It does not confirm that the chain was anchored to the right question.

Many computer science findings assume the exponential time hypothesis is true. If it is not, the conclusions those findings establish about computational limits become useless. Fedor Fomin at the University of Bergen in Norway puts it plainly: a textbook he wrote on the subject would become obsolete if the finding holds. “This came as a complete surprise, a shock,” he says. “Nobody I know expected it.” [1]

The Objection That Has Not Yet Been Refuted

The most serious counterargument is not that the proof is wrong. It is that a proof and an explanation are different objects. Clément Canonne at the University of Sydney makes the point sharply: proving something and understanding why it is true are not the same thing. [1] Of the network of findings that leaned on the exponential time hypothesis, he says, “The web collapsed, and we looked behind. We have no idea why yet.” A result can be correct and still leave the field without a map.

Leslie Goldberg at the University of Oxford calls the claim an enormous breakthrough, assuming it is confirmed — and then draws a boundary that matters. The exponential time hypothesis is linked to P versus NP, the long-standing question of whether a problem whose answer is easy to check is also easy to solve. If the hypothesis were true, it would have implied the answer was no. But disproving it would not mean the answer is yes. “This doesn’t have a direct impact on P versus NP, so we should not view it as progress towards P versus NP,” Goldberg says.

OpenAI Says Its Models Have Toppled a 30-Year-Old Speed Limit for Computation (Image 1) — AI-generated image

There is a second objection, and it is about process rather than mathematics. Magnus Wahlström at Royal Holloway, University of London describes the phenomenon as “mathematics done by press,” worrying that proprietary models can suddenly overturn months of researchers’ work. Bart Jansen at the Eindhoven University of Technology in the Netherlands calls the work “ingenious,” “spectacular” and “awe-inspiring — but also humbling.” “It really makes you think about the future of mathematics, algorithms and academia,” he says. The result arrived in a blog post on 26 October, alongside other claimed breakthroughs in mathematics and physics.

OpenAI has commissioned an independent group to examine the findings, including Russell Impagliazzo and Ramamohan Paturi, both at the University of California, San Diego, who helped propose the hypothesis in the first place. In an open letter, the group says the work could “change an important part of theoretical computer science.”

The Precedent Sitting in the Same Announcement

The clearest signal of what to expect next is not in the computer science result at all. It is in the company’s own bundle. Alongside the exponential time hypothesis claim, OpenAI says its models proved a 1991 conjecture that waves cannot remain intensely focused for long. If confirmed, that would also answer enduring questions about how thin a shape can be while still containing line segments pointing in every direction, and about how waves spread. The announcement also claims a proof that quantum field theories — including quantum chromodynamics, which describes the strong force holding quarks together — make sense mathematically, rather than merely producing predictions that match experiments. That work touches on the existence of pure Yang-Mills theory — a mathematical formulation of certain field theories, part of a million-dollar mathematical problem — but does not resolve the whole challenge. It has not been released publicly while an external group led by Nobel laureate David Gross examines it.

The computer science claim, the wave conjecture, the field theory claim: each one is a long-standing open problem, and each one is held back or hedged pending outside review. The same announcement applies one template across three fields at once: a claim, a formal check, then an independent panel that the claimant itself convened.

Fomin, for one, welcomes the disruption rather than resenting it. “This result destroys a lot, but it also opens many new opportunities and new questions that nobody expected,” he says. Wahlström lands on the same note from a different direction: “One shouldn’t complain about having too many interesting mathematical breakthroughs to try to digest.” The exponential time hypothesis took nearly 30 years to become an assumption. Whatever replaces it will have to survive the same slow chewing — and the first bite belongs to the people who proposed it.

Sources

OpenAI Says Its Models Have Toppled a 30-Year-Old Speed Limit for Computation (Image 2) — AI-generated image

Newscientist — Quote source (original article) Mentioned organisations (context, not sources)