AI Labs Claim to Refute Exponential Time Hypothesis
Original: Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
Why This Matters
A proven ETH refutation would upend decades of assumptions about computational hardness.
OpenAI released solutions to three major math problems on Oct. 26, 2026, including a refutation of the Exponential Time Hypothesis. Hours later, Anthropic published its own competing refutation, triggering debate across the computer science community.
OpenAI dropped solutions to three long-standing math problems on GitHub, with the most significant being a claimed refutation of the Exponential Time Hypothesis (ETH) — a foundational assumption in computational complexity theory first published in 1999 by UC San Diego researchers Russell Impagliazzo and Ramamohan Paturi. The ETH sits within the broader P vs NP problem, which asks whether problems whose solutions are easily verified can also be easily solved. Practical implications run deep: modern cryptography depends on certain problems being hard to crack even when verification is fast.
The release triggered swift controversy. Anthropic mathematician Levent Alpöge accused OpenAI of building on pre-existing work, and Anthropic released its own ETH refutation within hours. OpenAI structured this release differently than its earlier October proof dump — which MIT Professor Ryan Williams had called a "DDOS attack on mathematicians" — by engaging separate working groups for mathematicians, computer scientists, and physicists. Williams, who agreed to help interpret the computer science result alongside Impagliazzo and Paturi, described parts of OpenAI's proof as "alien-looking" and called for community-wide scrutiny. A working group has issued an open letter inviting scientific feedback and pushing for norms around AI-generated mathematical contributions.