AI labs claim their models refuted a core complexity assumption

OpenAI posted solutions to three long-standing math problems, and one of them takes aim at the Exponential Time Hypothesis, a conjecture that sits inside the P versus NP question. ETH holds that a certain class of hard logic puzzles needs exponentially more time to solve as the number of variables grows. The labs say their models found algorithms that run in sub-exponential time instead, which is faster than anyone thought possible. Hours after an Anthropic mathematician suggested OpenAI had leaned on existing work, Anthropic published its own refutation on GitHub. Russell Impagliazzo and Ramamohan Paturi, who first proposed ETH in 1999, are now helping interpret the results.

The claims are not confirmed. MIT's Ryan Williams, who is organizing the field's response and earlier called OpenAI's proof dump a "DDOS attack on mathematicians," says the algorithm is probably not optimal and that parts of the proof read as routine while a few look "alien." The practical stakes are real. Many papers assume ETH and would need revisiting if it falls, and Williams warned that a better algorithm could threaten cryptosystems built on specific key sizes. OpenAI science lead Dan Roberts reportedly checked and was "reasonably confident" no breaks followed. The episode is as much about process as math: the labs are testing how to release AI-driven results, posting some to GitHub, forming working groups for others, and asking researchers to set norms for credit and review. The TechCrunch account lays out the full timeline.

Why it matters

If your work rests on complexity assumptions or on cryptographic key sizes, this is worth watching closely, though nothing is settled yet. For everyone else, it is an early test of how the field will check and credit mathematics that a model produced.