OpenAI and Anthropic Claim Their Models Refuted the Exponential Time Hypothesis, and Theorists Are Checking the Proofs

OpenAI says its model has refuted the Exponential Time Hypothesis (ETH), one of the durable assumptions of theoretical computer science. According to TechCrunch, Anthropic then published its own refutation of the same hypothesis. Neither result has yet been confirmed by independent researchers.

What the ETH Is

ETH is tied to the P versus NP question. According to TechCrunch, it holds that a certain class of tricky logic puzzles requires exponentially more time as the number of variables grows. The labs say their models found algorithms that solve those puzzles in sub-exponential time.

If the claims hold up, ETH is refuted, and according to TechCrunch that could open a path toward algorithms in the spirit of P = NP. Many papers from the past decade rely on ETH, so they would need to be revisited if the result is confirmed.

A Dispute Over Priority

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

So two companies now say their models refuted ETH. It is not yet clear how the two approaches relate to each other, and the assessment is up to researchers.

How Verification Works

OpenAI structured the release differently for each discipline. Mathematicians got the work on GitHub. Computer scientists formed a working group, asked for the proofs to be made public and for OpenAI to fund a conference. Physicists have their own group, which will decide how their result is released.

The computer science response is coordinated by MIT professor Ryan Williams, together with Impagliazzo and Paturi, who first published ETH in 1999. They issued an open letter asking the community for feedback and for a discussion of norms around AI contributions. Williams had earlier called OpenAI's flood of proofs a “DDOS attack on mathematicians,” but agreed to collaborate anyway.

“Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one’s weight may vary.” - Ryan Williams, MIT professor

Experts Urge Caution

Williams said the proof contains “two or three alien-looking parts” that convinced him the community has to work on it together. He also doesn't think the algorithm found could be the best possible one. In his view AI is “forcing people to be a little more ambitious,” but he is also concerned about training the next generation of scientists.

Williams asked Dan Roberts, who leads science at OpenAI, whether the result affects any cryptographic systems. According to Williams, OpenAI apparently checked and was “reasonably confident” that the result does not imply any breaks.

What Comes Next

The coming weeks will show whether the refutation of ETH survives independent scrutiny. For Polish readers, it is above all a signal that AI labs are starting to publish results in mathematics and theoretical computer science faster than the scientific community can check them.