OpenAI and Anthropic say their AI systems have produced algorithms that challenge the Exponential Time Hypothesis (ETH), a long-standing idea about how quickly certain difficult problems can be solved. The claims are prompting computer scientists to examine both the proofs and what they could mean for the field.
ETH predicts that for a particular class of logic problems, the fastest algorithms need exponentially more time as the number of variables increases. The new approaches are described as running in "sub-exponential" time, which would be faster than the hypothesis allows. Their results have not yet settled the question: researchers are still working to verify and understand the proofs.
Why the hypothesis matters
ETH is connected to the wider P versus NP question: whether problems whose solutions can be checked quickly can also be solved quickly. For example, checking a completed Sudoku puzzle is straightforward, while finding a solution can take much longer. ETH has helped researchers reason about the limits of algorithms and has informed work across computer science.
MIT computer scientist Ryan Williams is working with colleagues, including UC San Diego researchers Russell Impagliazzo and Ramamohan Paturi, to coordinate a community response. The researchers are seeking feedback and discussion on how AI-generated contributions should be evaluated and shared. OpenAI and Anthropic have each presented a proposed refutation.
If the findings hold up, researchers may need to revisit studies that rely on ETH and reconsider assumptions about the difficulty of some computational problems. Williams has also raised questions about possible implications for cryptography; OpenAI said it had checked for immediate security consequences and did not believe the result implied that any systems had been broken.
The proofs remain under scrutiny, but the episode points to AI becoming a more active partner in mathematical discovery. If validated, such work could reshape how scientists explore difficult problems and set new standards for collaboration between people and AI.
