OpenAI and Anthropic say their models refuted a key CS hypothesis

OpenAI published solutions to three long-standing math problems, among them a surprise refutation of the Exponential Time Hypothesis (ETH) — a foundational assumption in computer science about how hard certain problems are to solve. As with earlier proof releases from the lab, the reaction mixed excitement with unease: Anthropic mathematician Levent Alpöge argued that OpenAI’s solutions leaned on work that already existed, and within hours Anthropic put out its own ETH refutation.

This time, OpenAI varied its rollout by field: it posted the math results on GitHub, offered computer scientists a working group and funding for a conference on the proofs, and left physicists to form their own working group on how to release their result. The shift followed criticism from MIT professor Ryan Williams, who leads the computer-science field’s response and had previously likened an earlier October proof dump from OpenAI to a denial-of-service attack on mathematicians. Williams still agreed to help interpret the new result, alongside UC San Diego’s Russell Impagliazzo and Ramamohan Paturi, who published the original ETH paper in 1999; the group’s first move was an open letter asking the field for feedback on the math and on the norms for AI contributions to it.

ETH sits inside the broader P-versus-NP question: whether every problem whose solution is easy to check (NP) is also easy to find (P) — the logic behind cryptography, where reading an already-decoded message is trivial but cracking the code is not. Most scientists assume P does not equal NP, and ETH backed that assumption by holding that no algorithm can solve a specific class of hard logic puzzles without the time needed growing exponentially as the puzzle grows. OpenAI and Anthropic say their models produced algorithms capable of solving those puzzles in “sub-exponential” time — faster than researchers thought possible — and, if the result holds, it would refute ETH and could open a path toward proving P equals NP after all.

“Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one’s weight may vary,” Williams said, though he doubts OpenAI’s algorithm is the best one that exists. The result threatens a decade of papers built on ETH’s durability, which is why Williams pushed OpenAI to help fund a conference on the fallout. He also raised a sharper, near-term worry: whether a faster algorithm breaks cryptography that relies on specific key sizes. He put that question directly to OpenAI science lead Dan Roberts, and the lab checked back reasonably confident nothing had broken. Williams says he remains optimistic about AI’s expanding role in research, even as it pushes scientists to raise the bar on the kinds of questions they ask.

Why it matters

If the sub-exponential algorithms hold up under scrutiny, a decade of papers built on ETH’s durability — and potentially some cryptographic systems that lean on it — would need a second look, underscoring how fast AI labs can now unsettle foundational fields.