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

OpenAI released proposed solutions to three major mathematics and science problems, including a claimed refutation of the Exponential Time Hypothesis, or ETH. Anthropic mathematician Levent Alpöge questioned whether OpenAI’s solutions drew on existing work, and Anthropic later released its own claimed ETH refutation. MIT computer scientist Ryan Williams, UC San Diego’s Russell Impagliazzo, and Ramamohan Paturi—who first published ETH in 1999—are helping organize an expert response and have called publicly for feedback. ETH holds that a class of hard logic problems requires exponentially increasing time to solve as the number of variables grows. It supports the widespread intuition that P differs from NP: solutions to certain problems may be quick to verify but not quick to find. OpenAI and Anthropic claim their models produced sub-exponential algorithms for such problems. If the claims withstand review, they would invalidate ETH and could increase the perceived plausibility of P equaling NP, though Williams said OpenAI’s algorithm is unlikely to be the best possible one. Williams said papers that rely on ETH may need reassessment. He also raised possible cryptographic consequences; OpenAI science lead Dan Roberts told him the lab had checked for effects on cryptographic systems and was reasonably confident the result did not make any insecure. Computer scientists have asked OpenAI to share the proof publicly and fund a conference to evaluate its implications.