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

OpenAI and Anthropic say their AI systems produced proofs refuting the Exponential Time Hypothesis (ETH), a long-standing assumption that certain computational problems cannot be solved quickly as they grow. If the result holds up, it could change how computer scientists understand the limits of efficient computation, though researchers are still examining the proof.

MIT computer scientist Ryan Williams is coordinating a response with researchers Russell Impagliazzo and Ramamohan Paturi, who introduced ETH in 1999. Williams described parts of OpenAI’s proof as unusual and called for community feedback and discussion of standards for AI contributions; OpenAI has also proposed funding a conference. The article frames ETH within the wider P versus NP question, which asks whether problems whose answers can be checked quickly can also be solved quickly.