OpenAI and Anthropic claim their models refuted the Exponential Time Hypothesis

OpenAI says its models have refuted the Exponential Time Hypothesis (ETH), a long-standing assumption in computer science about how hard certain problems are to compute. According to TechCrunch, the lab released solutions to three math problems yesterday, and Anthropic released its own refutation of ETH hours after OpenAI's release.

What the labs claim

ETH says that even the fastest algorithm needs exponentially more time to find a solution as the number of variables grows, in a specific class of tricky logic puzzle. OpenAI and Anthropic claim their models produced algorithms that solve those puzzles in "sub-exponential" time, meaning faster than previously thought possible. If the claims hold, ETH is false. That could also open a path toward algorithms that generally achieve P = NP.

ETH was first published in 1999 by Russell Impagliazzo and Ramamohan Paturi, both computer scientists at UC San Diego. It is part of the broader P vs NP family of problems, which asks whether any problem whose solution can be quickly verified can also be quickly solved. Most scientists assume P does not equal NP, and ETH is considered evidence for that.

A dispute over provenance

Anthropic mathematician Levent Alpöge suggested that OpenAI based its solutions on pre-existing work. Hours later, Anthropic released its own refutation of ETH.

Different release paths for each field

OpenAI structured the three releases differently:

• Mathematicians: the work was posted on GitHub.
• Computer scientists: formed a working group, asked for the proofs to be shared publicly, and asked OpenAI to fund a conference to discuss them.
• Physicists: formed a working group that will determine how their result is released.

MIT Professor Ryan Williams is organizing the computer science response. He previously called an earlier OpenAI proof dump in October a "DDOS attack on mathematicians," but agreed to collaborate with the labs. OpenAI asked him to help interpret the solution, along with Impagliazzo and Paturi. Their first step was an open letter requesting feedback from interested scientists and a discussion of norms around AI contributions.

"Some parts [of OpenAI's proof] are, maybe you could say routine, but then yes, there are two or three alien-looking parts," Williams told TechCrunch. He said those parts convinced him the whole community needs to work on the result together.

Security and downstream effects

Williams said an improved algorithm could imply that cryptographic systems relying on certain key sizes are broken. He said he asked OpenAI science lead Dan Roberts whether the team had checked for effects on crypto systems. According to Williams, OpenAI checked and was reasonably confident the result does not imply any breaks.

He also said ETH appears in many papers from the past decade, and those will need revisiting if the labs' claims hold up. He said this is part of why he pushed OpenAI to support a conference.

Williams does not regard the result as final. "I don't think that OpenAI's algorithm could possibly be the best algorithm you can get," he said. He added that computer scientists should probably put more weight on the plausibility of P = NP, though that weight may vary.

What this means

The refutation of ETH is still a claim under community review, not an accepted result. Both OpenAI and Anthropic have published one, and a working group of computer scientists is now collecting feedback and setting norms for how AI-generated work is evaluated. Williams says the result calls into question intuitions about how tractable hard NP problems are, and that papers built on ETH may need to be re-examined. On the cryptography question, the only assurance cited is OpenAI's own check, relayed by Williams. Williams also says AI is pushing researchers to ask more ambitious questions, since work they once did may now be low-hanging fruit for AI.