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
“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.”
For centuries, science has advanced through making hypotheses and proving them wrong.
It also isn’t unusual for an academic to be scooped or have their work otherwise undercut by another research group. But AI has accelerated this, obliterating whole research programs and spooking researchers in specific fields of math and science who wonder where they stand now that machines can outperform them. “The last few months have been really tough. It’s a lot of doom and gloom, because every week, or every second week, the results announced by AI just annihilate the ongoing research projects of many people,” Husfeldt says.
That is psychologically taxing for many people, he
“That is psychologically taxing for many people,” he says, adding that his department has considered hiring an occupational psychologist because “some people are really depressed and really sad.”
Researchers have also been overwhelmed by the volume of content now being produced, thanks to AI, including slop-level results. Midway through the interview, Husfeldt receives what he suspects to be an AI-generated 17-page paper on the consequences of the ETH result from a random Gmail account.
He won’t read it: “Reading math is a very big investment of cognitive time,” he says. OpenAI has directly contributed to this; earlier this month, it dumped 722 manuscripts on 400 problems on GitHub, to the annoyance of academics, who complain this makes it difficult to digest the results. Adding to the frustration were several documents that contained errors, reflecting what some mathematicians saw as a hasty rollout designed to juice the company’s planned initial public offering rather than moving the field forward.
This time around, OpenAI’s 60-odd-page paper on ETH seems to be written better than the companies’ past publications, academics tell WIRED. They are now scrambling to unpack the paper and find what other results they can quickly deduce from it. If ETH is false and it doesn’t, in fact, take exponentially more time to solve problems as they become more complex, that’s “exciting,” says Victor Lagerkvist, an associate professor at Linköping.
He plans to return to problems he had
He plans to return to problems he had previously given up on under the assumption ETH was accurate. OpenAI’s finding could also have impacts on the cryptography that underpins web security, which is based on the assumption that certain mathematical problems take an impractically long time to solve. While this particular result doesn’t directly affect cryptography, “it should definitely scare some cryptosystem designers,” says Lokshtanov.
That’s why continued human and AI-assisted work in theoretical computer science is important, Husfeldt adds: “We want the open scientific process to identify our misunderstandings about computation, in particular because lots of modern digital infrastructure is built on assumptions about computation.”
As for Linköping’s Jonsson, he plans to revisit both his own and others’ papers that hinge on ETH being true, and believes his conference paper may eventually be salvageable through another method.
He’s excited to look into the details of OpenAI’s proof and see what he can learn from it and apply it to new problems. Even though it undoes the assumptions underpinning his work, having a verdict for ETH is something he could only “dream of” before, he says. “These are exciting times,” he adds. “Most people would never experience anything like this in their career.”
“I don’t care if it’s a human-written proof, or it’s written by AI, or if an alien transmitted this proof to us.
If it’s true, then we must simply use it in the future.’’
