Linköping University professor Peter Jonsson is set to have his work presented in two weeks’ time at one of the most prestigious conferences in theoretical computer science. As of Monday, much of that work is “dead,” he says, after AI showed that a 27-year-old hypothesis underpinning it is wrong.
Both OpenAI and Anthropic claimed this week to have disproved the exponential time hypothesis (ETH). Vast swaths of theoretical computer science research on complexity and algorithm design have been built on the premise that the effort it takes to solve certain problems increases exponentially with the size of the problem.
Jonsson expects his predicament will be “very common” at the IEEE Symposium on Foundations of Computer Science, where his work will be presented by one of his coauthors. “People will start the talks: ‘ETH is false, half of my paper does not work,’” he says. It’s a vexing problem, Jonsson says, “but at the same time, we learn a lot from it. And this is what science is about.”
Researchers haven’t independently verified, let alone had time to fully understand, the AI-produced proofs, which both firms have published on GitHub in both natural language and its machine-checkable Lean format. OpenAI has asked the UC Santa Barbara computer scientists who originally proposed the hypothesis, plus an MIT academic who has refuted a version of ETH, to rally researchers to unpack the proofs. So far, this effort includes a Google form asking for volunteers and feedback, and a commitment from OpenAI to fund a conference on the topic.
UC Santa Barbara professor Daniel Lokshtanov plans to join the effort, as he estimates the result—if confirmed—will render him “galactically wrong” and make around 50 of his published papers either “pointless” or in need of a revisit.
“It’s just a giant bomb dropped into the middle of the field,” he says. “It’s really cool and terrible at the same time.”
Thore Husfeldt, head of the algorithms research group at the IT University of Copenhagen, had spent most of this year thinking about one single problem in his subfield. “As far as I can tell, it’s now all irrelevant,” he tells WIRED. Having first formulated a version of the hypothesis now disproved by OpenAI, he has been writing calculations on his blackboard to figure out what other parts of his work might have become obsolete due to the “once-in-a-generation result.” Unlike the ennui that has gripped math researchers who have faced similarly field-upending proofs generated by AI models, though, Husfeldt expressed enthusiasm about the new results.
The finding is “fantastic,” he says. “Being a mathematician is a lot like stumbling about in a completely dark room,” he explains. “It’s like somebody just illuminated an entire subfield in floodlights of knowledge, and now we just run around like overexcited bunnies and look at all the nooks and crannies that we can suddenly explore. So it’s a super exciting time.”
