OpenAI and Anthropic said this week that AI impacts theoretical computer science by disproving the exponential time hypothesis, a claim that cuts into a foundation used across complexity and algorithm design. If the result holds, work built on that assumption may need major revision rather than minor correction.
Peter Jonsson on a dead body of work
Peter Jonsson, a Linköping University professor, said much of his work was “dead” after AI showed that a 27-year-old hypothesis underpinning it is wrong. He said, “but at the same time, we learn a lot from it. And this is what science is about.”
OpenAI, Lean, and the proofs
OpenAI posted the proofs on GitHub in natural language and in Lean format, which gives researchers two ways to inspect the same argument: one for reading and one for machine checking. The company also asked the UC Santa Barbara computer scientists who originally proposed the hypothesis and an MIT academic who has refuted a version of ETH to help unpack the proofs, and it has committed to funding a conference on the topic.
Why the field is uneasy
The proofs have not yet been independently verified, so the field is stuck between a potential rewrite of decades of work and a result that still needs careful scrutiny. Daniel Lokshtanov said the claim could render around 50 of his published papers either “pointless” or in need of a revisit if it is upheld, while Thore Husfeldt said, “As far as I can tell, it’s now all irrelevant,” and called it a “once-in-a-generation result.”
Jonsson’s own paper is set to be presented in two weeks' time at the IEEE Symposium on Foundations of Computer Science, where he said, “People will start the talks: ‘ETH is false, half of my paper does not work,’” a line that captures the immediate practical problem for researchers planning talks, papers, and revisions. For now, the unanswered question is whether the AI-produced proofs will survive independent expert verification, because that determines whether the disruption stays a startling claim or becomes a settled change in the field.
