Two AI Labs Claim Their Models Refuted a Core Computing Assumption
OpenAI and Anthropic have each released work claiming their AI models found algorithms that break a long-standing assumption about the limits of computation — a claim that, if it holds, could ripple through cryptography and decades of computer science research.
The disputed idea is the Exponential Time Hypothesis, or ETH, first published in 1999 by Russell Impagliazzo and Ramamohan Paturi of UC San Diego. It holds that for a certain class of hard logic puzzles, even the fastest possible algorithm needs exponentially more time as the problems grow. The ETH has been a load-bearing assumption in computer science for over two decades, underpinning how researchers think about what is genuinely difficult to compute.
Both labs now claim their models produced algorithms that solve those puzzles in "sub-exponential" time — faster than previously thought possible. If verified, that would refute the ETH and nudge the field toward the unsettling possibility that P equals NP: that any problem whose answer can be checked quickly can also be solved quickly. That would be a big deal. Modern cryptography rests on the assumption that some problems are easy to verify but practically impossible to solve without the right key. MIT professor Ryan Williams, who is organizing his field's response, said one of his first questions to OpenAI was whether the result breaks any cryptographic systems. The lab checked and was "reasonably confident" it does not.
The most striking detail is how differently the scientific community is handling this compared with earlier AI proof-drops. Williams previously called OpenAI's October release a "DDOS attack on mathematicians." This time, computer scientists formed a working group, asked for the proofs to be shared publicly, and pushed OpenAI to fund a conference. Williams said parts of the proof look routine, but "two or three alien-looking parts" convinced him the whole community needs to work on it together. He also said many papers built on the ETH over the past decade would need revisiting if the claim holds.
Williams remains cautious: he does not think OpenAI's algorithm is the best possible, and he says the result is "probably not the final answer." But he told TechCrunch that every computer scientist should now put "a little more weight on the plausibility of P = NP."