Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?

OpenAI says it has found solutions to three major math problems, and one of them is a direct hit on the Exponential Time Hypothesis, or ETH. That matters because ETH has been one of the sturdier assumptions in computer science for years: the idea that certain hard problems really do take exponentially longer as they get bigger. If AI labs have found sub-exponential algorithms for those problems, then a lot of familiar thinking about what is hard may need to be rewritten.

The reaction was immediate and messy, which is becoming a pattern. Anthropic’s Levent Alpöge suggested OpenAI may have leaned on earlier work, and within hours Anthropic put out its own refutation of ETH. Ryan Williams of MIT, who is helping organize the computer science response, has been publicly critical of OpenAI’s earlier proof dump, but this time he agreed to work with the lab. OpenAI also handled the three fields differently: mathematicians got the work on GitHub, computer scientists formed a working group and asked for the proofs to be shared publicly along with funding for a conference, and physicists are still deciding how their result should be released.

Williams was brought in alongside UC San Diego’s Russell Impagliazzo and Ramamohan Paturi, who first published ETH in 1999. The group has already published an open letter asking for feedback from scientists and calling for a discussion about the rules around AI-generated contributions. Williams said some of the proof looked routine, but a few parts looked “alien,” and those are the bits that convinced him the field needs to work through this together.

ETH sits inside the broader P versus NP problem, which asks whether problems that are easy to check are also easy to solve. The classic example is Sudoku: a finished grid is quick to verify, but filling one in is a grind. ETH gave researchers a reason to believe that some of these problems stay stubbornly hard, and OpenAI and Anthropic are now claiming their models found faster ways through at least one of them. Williams said that should make computer scientists take P = NP a little more seriously, while also warning that this probably is not the final answer.

There is also a security angle. If a better algorithm really lands, it could force researchers to revisit older papers and ask whether any cryptographic systems are weaker than expected. Williams said he asked OpenAI whether they had checked for crypto breakage, and the company was apparently confident that nothing was rendered insecure. For now, the bigger shift may be cultural: AI is pushing scientists to aim higher, because some of the old low-hanging fruit may no longer be safely theirs.