Frontier AI labs claim to refute the Exponential Time Hypothesis

OpenAI announced it had solved three major math problems, including a refutation of the Exponential Time Hypothesis (ETH), a foundational assumption in theoretical computer science. According to the announcement, its models produced algorithms solving NP problems in "sub-exponential" time, faster than ETH previously allowed. Anthropic quickly followed with its own ETH refutation, sparking mixed reactions in the scientific community.

OpenAI tailored its releases by discipline: GitHub for mathematicians, a working group for computer scientists, and another for physicists. MIT Professor Ryan Williams, an expert in algorithmic complexity, previously criticized OpenAI’s methods but now collaborates with the lab to analyze these findings. He notes that parts of OpenAI’s proofs appear innovative, while others rely on existing work. Researchers are calling for collective discussion to assess the impact of these discoveries.

ETH is tied to the P vs NP problem, a decades-old challenge in computer science. If OpenAI and Anthropic’s results hold, they could challenge theoretical foundations used in many scientific papers and have implications for cryptography. Williams urges caution, suggesting these results are likely not final and highlighting educational and methodological challenges posed by AI in fundamental research.