OpenAI and Anthropic say AI found faster algorithms for hard problems

A claim that needs a field to check it

The Exponential Time Hypothesis, or ETH, says that certain hard logic problems require exponentially more time to solve as the number of variables grows. OpenAI and Anthropic say their models found algorithms that solve those problems in subexponential time—faster than ETH allows.

The claim connects to the broader P versus NP problem: whether every problem whose solution can be checked quickly can also be solved quickly. Sudoku offers a simple analogy. Checking a completed grid is easy; finding a solution can take much longer. If P equaled NP, every problem with quickly checkable answers would also have a fast solution.

Most researchers expect P ≠ NP. ETH has served as evidence for that view, though it is not a proof of P ≠ NP. If the labs’ results are confirmed, they could undermine ETH and strengthen the case for algorithms that support P = NP.

OpenAI asked MIT professor Ryan Williams to review its result alongside computer scientists Russell Impagliazzo and Ramamohan Paturi of the University of California, San Diego. Impagliazzo and Paturi first published ETH in 1999. Williams had criticized OpenAI earlier in October for releasing a large volume of proofs, calling it a “DDoS attack on mathematicians.” He nevertheless agreed to help examine work that could affect his field.

Williams told TechCrunch that parts of OpenAI’s proof look routine, but that two or three elements are unfamiliar enough to warrant discussion across the discipline. He and other computer scientists first issued an open letter inviting researchers working on these problems to weigh in and discuss norms for using AI contributions in research.

The labs have taken different routes to circulating their claims across disciplines. OpenAI put the mathematics paper on GitHub. Computer scientists formed a working group, asked for the proofs to be opened up, and sought funding for a conference. Physicists also formed a working group to decide how to publish their result.

The proof is only the beginning

ETH has appeared in research papers for decades. If the new claims survive scrutiny, Williams says, many of those papers may need revisiting. The challenge is not just to understand the algorithms, but to work out what they change about the assumptions underlying the field.

Williams thinks computer scientists should take the plausibility of P = NP somewhat more seriously, even if they differ on how much confidence to place in it. He is not calling the question settled: he doubts OpenAI’s algorithm is the best possible.

The implications could extend beyond theory. A more efficient algorithm might threaten cryptographic systems that use keys of certain lengths. Williams said one of his first questions to OpenAI research lead Dan Roberts was whether the company had checked for effects on cryptography and found any systems unsafe. According to Williams, OpenAI had done that review and was confident the algorithms did not amount to breaking cryptographic systems.

That reassurance narrows one immediate concern, but it does not answer the broader question of what happens if the underlying claims hold. I think the more consequential test is whether other researchers can reproduce the reasoning—and whether the field can absorb a result that could unsettle decades of work without treating the AI contribution as either a shortcut or a threat.

Williams is optimistic about AI’s role in research, despite concerns about how it may affect the next generation of scientists. He says AI is encouraging researchers to take on more ambitious problems and reconsider what to study when tasks that once seemed difficult become easy for AI. The tension is that a tool capable of changing the questions researchers ask still has to earn trust in the answers it offers.