For nearly three decades, a hypothesis called the Exponential Time Hypothesis sat quietly at the foundation of theoretical computer science. Not a law, not a theorem, but an assumption so widely accepted that entire fields of research were built on top of it. OpenAI now claims its AI models have produced an algorithm that disproves it. If the finding holds, the consequences reach far beyond any single research paper.
What the Exponential Time Hypothesis Actually Said
The Exponential Time Hypothesis, proposed roughly 30 years ago, addresses a deceptively simple question: how fast can a computer solve certain logical puzzles? The most straightforward approach is brute force, testing every possible combination of true or false for each variable in the puzzle. ETH did not claim this was the only way. It acknowledged that shortcuts exist. What it proposed was a floor: no matter how clever the shortcut, the computational work required must still grow exponentially as the puzzle grows larger.
This sounds technical, but the practical implication is significant. ETH was essentially a speed limit on a class of problems. It told researchers what was, in principle, achievable, and what was not. Entire branches of algorithms and complexity theory were developed with that limit as a given.
OpenAI says its models have devised an algorithm that beats that assumed speed limit. The claim is that ETH is false.
The Cascade Effect: What Breaks When a Foundation Shifts
This is what most coverage of the announcement misses. The story is not just about one hypothesis being wrong. It is about what was built on top of it.
Fedor Fomin at the University of Bergen describes the reaction among researchers as a complete shock. He notes that a textbook he wrote on the subject would become obsolete if the finding is confirmed. That is not hyperbole. Many computer science conclusions were derived by assuming ETH was true. If the assumption falls, those conclusions no longer hold. As Fomin puts it, the result would require a complete revision of several areas of algorithms and complexity.
Leslie Goldberg at the University of Oxford calls it, conditionally, an enormous breakthrough. The condition matters: the finding still needs to be verified and, crucially, understood. Stefan Szeider at TU Wien has reviewed what OpenAI has released and expects it to withstand scrutiny, but notes that researchers still need to confirm the formally proven statement means what its authors say it means. That distinction, between a proof being technically valid and a proof meaning what you think it means, is not a minor one.
ETH is also connected to one of the most famous open problems in mathematics: P versus NP. This concerns whether problems whose answers are easy to check are also easy to solve. ETH being true would have implied the answer is no. But Goldberg is explicit: disproving ETH does not mean the answer is yes. The P versus NP question remains open.
OpenAI used Lean, a software tool that formally checks mathematical proofs, to verify the ETH result. It has also commissioned an independent review group that includes Russell Impagliazzo and Ramamohan Paturi, both at the University of California, San Diego, who were among the researchers who originally proposed ETH. Their open letter describes the finding as something that could change an important part of theoretical computer science.
Mathematics Done by Press, and Why That Phrase Matters
The ETH result was not the only announcement. OpenAI also claims its AI proved a 1991 conjecture about wave behavior, with implications for how waves spread and how thin a shape can be while still containing line segments pointing in every direction. In theoretical physics, it claims to have proven that quantum field theories, including quantum chromodynamics, which describes the strong force that holds quarks together, are mathematically coherent rather than just experimentally useful. Work touching on the existence of pure Yang, Mills theory, part of a million-dollar mathematical problem, has not been released publicly while a group led by Nobel laureate David Gross examines it.
The breadth of these announcements has generated unease in academic circles. Magnus Wahlström at Royal Holloway, University of London, describes the phenomenon as “mathematics done by press,” raising concern that proprietary AI models can suddenly overturn months of researchers’ work without the usual process of peer review and gradual verification.
Clément Canonne at the University of Sydney draws a sharp distinction that is worth holding onto: proving something and understanding why it is true are not the same thing. The network of findings that relied on ETH has collapsed. Why it collapsed remains unknown.
In Short
A hypothesis that shaped theoretical computer science for 30 years may have been disproven by an AI model. If confirmed, the implications are structural: conclusions built on ETH across algorithms and complexity theory would need to be revisited. The finding is under independent review, including by researchers who originally proposed the hypothesis. What makes this moment genuinely unusual is not just the result itself, but the gap it reveals: AI systems can now produce proofs that humans cannot yet fully explain. That gap between proof and understanding is where the real work begins.
Based on reporting from New Scientist.