Peter Jonsson, a professor at Linköping University, says an AI-generated proof challenging the Exponential Time Hypothesis (ETH) has potentially overturned years of theoretical computer science research. With Jonsson scheduled to present related work at a major conference in two weeks, he says much of that research was effectively “dead” as of Monday—although the proof has not yet been independently verified or fully understood.
An AI challenge to a foundational hypothesis
Both OpenAI and Anthropic claimed this week that ETH has been disproved. The 27-year-old hypothesis underpins a large body of research into computational complexity and algorithm design, based on the premise that solving certain problems requires effort that grows exponentially with the size of the input.
Jonsson expects his situation to be “very common” at the IEEE Symposium on the Fundamentals of Computer Science, where one of his co-authors will present their work.
“People will start negotiations saying, ‘ETH is a lie, half of my paper doesn’t work,’” he says. “This is a tricky problem, but at the same time we can learn a lot from it. And this is science.”
Researchers are still examining the AI-generated proof
Researchers had not independently verified the proof, nor had they had time to understand it fully. The companies published it on GitHub in both natural-language and machine-checkable Lean formats.
OpenAI asked the computer scientist at the University of California, Santa Barbara, who first proposed the hypothesis, along with the MIT academic who refuted a version of ETH, to bring researchers together to examine the evidence. So far, the effort includes a Google Form seeking volunteers and feedback, as well as a commitment from OpenAI to fund a conference on the subject.
Daniel Rokshtanov, a professor at the University of California, Santa Barbara, who will participate in the effort, estimates that if the results are confirmed, he would be “galactically wrong.” He says about 50 of his published papers could become “senseless” or require reconsideration.
“It was just a huge bomb dropped in the middle of a field,” Rokshtanov says. “It’s really cool and scary at the same time.”
A potentially transformative result
Tor Hasfelt, head of the Algorithms Research Group at Copenhagen IT University, has spent much of this year working on a problem in one of his areas of expertise. “As far as I know, that’s all irrelevant now,” he told WIRED.
After first formulating a version of the hypothesis that OpenAI now claims to have disproved, Hasfelt continues to work through calculations on a blackboard to determine which other parts of his research may have been made obsolete by the “once-in-a-generation results.” Unlike Ennui, who has captivated mathematics researchers confronting similarly field-defying proofs produced by AI models, Hasfelt expressed enthusiasm about the findings.
“Being a mathematician is like stumbling around in a dark room,” he says. “It’s like someone shined a floodlight of knowledge across the entire subfield, and now we’re just running around like excited rabbits, looking around at all the nooks and crannies that we can suddenly explore. So it’s a very exciting time.”
Source: www.wired.com