AI Claims to Disprove Long-Standing Computational Complexity Hypothesis

Researchers at Linköping University and elsewhere are confronting the possibility that a core assumption in theoretical computer science may be invalid after OpenAI and Anthropic released AI-generated proofs that challenge the exponential time hypothesis (ETH). The hypothesis, which posits that solving certain problems requires time that grows exponentially with input size, underlies much of the field’s work on algorithm design and complexity.

Peter Jonsson, whose paper was slated for presentation at the IEEE Symposium on Foundations of Computer Science, said his results could become obsolete if the AI findings hold up. He expects many presenters to discover that “ETH is false, half of my paper does not work,” and described the situation as both vexing and a learning opportunity.

OpenAI has posted the proofs on GitHub in natural language and in the Lean proof-assistant format, and has invited the original proposers of ETH and other experts to help verify the work. A volunteer effort, coordinated through a Google form, includes participation from UC Santa Barbara professor Daniel Lokshtanov, who warned that confirmation could render dozens of his papers “pointless.”

“It’s just a giant bomb dropped into the middle of the field,” Lokshtanov said.

Thore Husfeldt of the IT University of Copenhagen, who has been focusing on related problems, described the result as “fantastic” and likened it to “someone illuminating an entire subfield in floodlights,” though he also noted the psychological strain on researchers facing rapid AI-driven disruptions.

“The last few months have been really tough. It’s a lot of doom and gloom…some people are really depressed and really sad,” Husfeldt said.

The volume of AI-produced manuscripts, including a recent 60-page paper on ETH, has overwhelmed academics, with some critics pointing to earlier releases that contained errors and appeared rushed.

Victor Lagerkvist, an associate professor at Linköping, said the potential falsification of ETH opens new avenues for problems he had previously set aside. Likewise, Lokshtanov cautioned that while the finding does not immediately threaten current cryptographic systems, it could eventually impact designs that rely on assumed computational hardness.

Researchers emphasize the need for continued human and AI collaboration to validate the proofs and explore their implications for computation and digital infrastructure.

“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,” a quoted researcher said.