A foundational pillar of theoretical computer science has been thrown into question following reports that artificial intelligence models from OpenAI and Anthropic have disproved the 27-year-old Exponential Time Hypothesis (ETH). For decades, the ETH has served as a bedrock assumption for researchers, positing that the computational effort required to solve specific problems grows exponentially as the problem size increases. If the AI-generated proofs are confirmed, vast swaths of existing academic research regarding complexity and algorithm design may be rendered obsolete.
The discovery has sent shockwaves through the scientific community, with experts describing the situation as a "giant bomb" dropped into the field. As researchers prepare for the upcoming IEEE Symposium on Foundations of Computer Science, many are bracing for a reality where their current work—and years of past publications—must be fundamentally re-evaluated or discarded.
The Impact on Academic Research
The potential invalidation of the ETH has created a complex predicament for academics worldwide. Peter Jonsson, a professor at Linköping University, noted that much of his current work, which is scheduled for presentation at a prestigious conference in two weeks, is now effectively "dead." He anticipates that many speakers at the event will be forced to open their presentations by acknowledging that their underlying premises have been disproved.
The scale of the disruption is significant. Daniel Lokshtanov, a professor at UC Santa Barbara, estimates that the result could render approximately 50 of his own published papers either pointless or in need of a major revision. Similarly, Thore Husfeldt of the IT University of Copenhagen noted that his research focus for the entire year has been rendered irrelevant by the new findings.
Verification and the Future of Proofs
Because the proofs were generated by AI, the scientific community is currently in a race to verify them. OpenAI and Anthropic have published their findings on GitHub in both natural language and a machine-checkable format known as Lean. To ensure rigor, OpenAI has initiated a collaborative effort, inviting the original proposers of the hypothesis and other experts to help unpack the proofs. This initiative includes a call for volunteers and a commitment from the company to fund a dedicated conference on the topic.
Despite the professional turmoil, many researchers remain optimistic about the long-term implications. While some academics have expressed concern over the "doom and gloom" atmosphere caused by AI’s rapid acceleration of research, others view the development as a breakthrough. Husfeldt compared the experience to having a dark room suddenly illuminated by floodlights, allowing mathematicians to explore new nooks and crannies of their field that were previously inaccessible.
Broader Implications for Digital Infrastructure
Beyond theoretical computer science, the potential collapse of the ETH carries implications for the security of modern digital infrastructure. Much of current cryptography relies on the assumption that certain mathematical problems are computationally difficult to solve. While this specific result does not immediately break existing cryptosystems, experts warn that it should serve as a wake-up call for designers to re-examine the assumptions underpinning digital security.
As the community works to digest the 60-plus-page proof, the consensus remains that the source of the discovery is secondary to its validity. As Jonsson noted, whether a proof is written by a human, an AI, or an external source, the priority for the scientific community is to integrate the truth into future research. For many, the opportunity to finally have a definitive answer on a decades-old hypothesis outweighs the frustration of having to rewrite their own work.
