OpenAI and Anthropic say AI disproved the exponential time hypothesis (opens the source in a new tab)
- OpenAI and Anthropic each said this week that their models disproved the exponential time hypothesis, a 27-year-old assumption that some hard problems take exponentially more effort as they grow. Both posted the proofs on GitHub, in plain language and in the machine-checkable Lean format.
- Independent researchers have not verified them yet. OpenAI has asked the UC San Diego scientists who proposed the hypothesis to rally volunteers and has promised to fund a conference.
- Reactions are split. Linköping's Peter Jonsson says much of his upcoming conference paper no longer works, while Copenhagen's Thore Husfeldt calls it a once-in-a-generation result but says the steady run of AI results has left colleagues demoralised.
- 27 yrs
- Age of the hypothesis the labs say is false
Why it matters If the proofs hold, a large body of theory built on the idea that certain problems cannot be solved quickly has to be redrawn. Cryptography rests on similar too-slow-to-solve assumptions, so its designers will be watching. It also shows AI labs now racing on frontier maths, not just chatbots.
Other side Nothing is settled until people check the proofs. Machine checking confirms the logic, but humans still have to confirm the formal statement says what the hypothesis says. And after earlier rushed AI paper dumps with errors, some academics suspect the labs time big claims to impress investors.