OpenAI and Anthropic said this week that they had disproved the exponential time hypothesis, a claim that could shake a large stretch of theoretical computer science if it survives independent review. The proofs were posted on GitHub in natural language and machine-checkable Lean format, but researchers have not yet verified them.
The reason the claim is landing so hard is that ETH has underpinned decades of work on complexity and algorithm design, and some researchers immediately saw their own papers in the blast radius. Peter Jonsson said as of Monday that much of his work was "dead" after AI showed that a 27-year-old hypothesis underpinning it was wrong. In two weeks’ time, his work is set to be presented at the IEEE Symposium on Foundations of Computer Science.
That reaction is not just about one paper. Daniel Lokshtanov said that if the result is confirmed, he could be "galactically wrong" and around 50 of his published papers would be either "pointless" or in need of a revisit. Thore Husfeldt, who first formulated a version of the hypothesis now said to be disproved, said that as far as he could tell, it was now all irrelevant. He called it a "once-in-a-generation result."
The pull between excitement and caution is already defining the moment. OpenAI 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 researchers unpack the proofs. The effort also includes a Google form for volunteers and feedback, and OpenAI has committed to fund a conference on the topic. But the central fact remains unresolved: the firms say they have proved ETH wrong, while the field has not yet independently confirmed how the arguments work, or whether they hold at all.
For now, that leaves theoretical computer science in an unusual place, with a claim that could rewrite parts of the field moving faster than the community can check it. If the proofs stand, years of complexity and algorithm design work will need to be revisited; if they fail, the episode will still have exposed how much of the field has been built on one assumption for 27 years and how quickly that assumption can be tested when the tools are new.
