Professor at Linköping University Peter Jonsson is expected to present his work in two weeks at one of the most prestigious conferences in theoretical computer science. As of Monday, much of that work has “died,” he says, after AI showed that a 27-year-old hypothesis underlying it was wrong.
OpenAI and Anthropic claimed this week to have disproved the exponential time hypothesis (ETH). Large swaths of theoretical computer science research on complexity and algorithm design have been built on the principle that the effort required to solve certain problems increases exponentially with problem size.
Jonsson expects his predicament to be “very common” at the IEEE Symposium on Foundations of Computing, where his work will be presented by one of his co-authors. “People will start discussions: ‘ETH is fake, half of my article doesn’t work,’” he says. It’s a tricky problem, says Jonsson, “but at the same time we learn a lot from it. And that’s the goal of science.”
Researchers have not independently verified, let alone had time to fully understand, the AI-produced evidence, which the two companies have posted on GitHub in both natural language and its machine-verifiable Lean format. OpenAI asked the UC Santa Barbara computer scientists who initially proposed the hypothesis, as well as an MIT academic who refuted an ETH version, to rally researchers to unpack the evidence. So far, that effort includes a Google form asking for volunteers and feedback, as well as a commitment from OpenAI to fund a conference on the topic.
Daniel Lokshtanov, a professor at the University of Santa Barbara, plans to join the effort because he believes the result, if confirmed, will make him “galactically false” and render about 50 of his published papers “useless” or in need of revision.
“It’s just a giant bomb dropped in the middle of the field,” he said. “It’s really cool and terrible at the same time.”
Thore Husfeldt, head of the Algorithmics Research Group at Copenhagen University of Computer Science, has spent most of this year thinking about a single problem in his subfield. “As far as I know, none of that matters anymore,” he told WIRED. After formulating a version of the hypothesis now disproven by OpenAI, he wrote calculations on his blackboard to determine what other parts of his work might have become obsolete due to the “once-in-a-generation result.” In contrast to the boredom that gripped math researchers who were confronted with equally overwhelming evidence generated by AI models, Husfeldt expressed enthusiasm for the new results.
The result is “fantastic,” he says. “Being a mathematician is a bit like stumbling into a completely dark room,” he explains. “It’s like someone just lit up an entire subfield with a knowledge spotlight, and now we’re running around like overexcited rabbits and looking at every nook and cranny that we can suddenly explore. So it’s a super exciting time.”
Gn bussni
