Two AI labs say their models have produced algorithms that challenge a long-standing idea about the limits of computation. The Exponential Time Hypothesis, or ETH, has helped researchers reason about which problems are especially difficult to solve. If the new claims withstand scrutiny, the implications could reach beyond the algorithms themselves.
What the hypothesis says about hard problems
The ETH sits within a larger set of questions about P versus NP. In simple terms, computer scientists ask whether every problem whose answer can be checked quickly can also be solved quickly. A Sudoku puzzle offers an intuitive example: checking a proposed solution is relatively quick, while finding one can take much longer.
The distinction also helps explain why cryptography can work. Someone with the right key can decode a message, while cracking an effective code without it is intended to take too long to be useful. The broader question is whether that gap between checking and solving applies to every problem in NP.
Most scientists have assumed that P does not equal NP. The ETH has supported that view by saying that, for a particular class of difficult logic puzzles, even the fastest algorithm needs exponentially more time as the number of variables grows. That is a statement about how the effort scales, not just whether a puzzle can eventually be solved.
Why the AI labs’ claim drew attention
OpenAI released solutions to three major math problems, including a result that it said refuted ETH. Anthropic also released its own refutation hours after Anthropic mathematician Levent Alpöge raised concerns that OpenAI’s solutions might draw on pre-existing work.
The claims center on algorithms that solve the relevant puzzles in “sub-exponential” time: a rate of growth faster than previously thought possible. If the algorithms and reasoning are sound, the results would challenge ETH. They could also lead researchers to give more weight to the possibility that P equals NP, though the source does not describe that broader question as settled.
MIT professor Ryan Williams is organizing the computer science response with UC San Diego computer scientists Russell Impagliazzo and Ramamohan Paturi, who first published ETH in 1999. Williams said some parts of the proof seemed routine to him, while two or three looked unfamiliar enough to warrant work by the wider community.
Reviewing the work together
The reception has mixed excitement with concern about how scientific results from AI labs are shared. OpenAI’s approach differed across the three disciplines involved: it posted the mathematicians’ work on GitHub, while computer scientists formed a working group and asked for public sharing of the proofs and funding for a conference. Physicists formed a group to decide how their result should be released.
Williams had criticized an earlier OpenAI proof release, calling it a “DDOS attack on mathematicians.” He nevertheless agreed to help interpret the computer science result. The group’s first step was an open letter seeking feedback from scientists and discussion about norms for AI contributions to research.
That review matters because ETH has been used in many scientific papers over the past decade. If the labs’ claims hold up, researchers may need to revisit work that relies on the hypothesis and decide what should replace it as a foundation. Understanding the proposed algorithms is only part of that task.
Questions for cybersecurity and future research
A faster algorithm can raise questions about cryptographic systems that rely on certain key sizes. Williams said he asked OpenAI science lead Dan Roberts whether the work affected any crypto systems. According to Williams, the lab had checked and was reasonably confident the result did not imply any breaks.
That answer addresses an immediate concern, while the broader implications still need examination. The source describes the AI approach to scientific discovery as a work in progress, and Williams said he remained optimistic despite concerns, including how the shift might affect the next generation of scientists.
He also suggested that AI could push researchers to aim higher: if some tasks they once pursued become easier for AI, they may need to ask more ambitious scientific questions. For computer scientists, the next steps are to scrutinize the algorithms, understand what the claims mean for existing research, and work out how the field’s assumptions should change if the refutation holds.