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

The Exponential Time Hypothesis has been a load-bearing assumption in computer science since 1999. It says certain hard logic puzzles can't be cracked much faster than brute force as they grow. OpenAI says its model found a sub-exponential algorithm that refutes it, and Anthropic followed hours later with its own refutation.

If the claim holds, a decade of papers that leaned on ETH will need a second look, and long-held intuitions about what is hard to compute get shakier. There is also a security question, because modern cryptography rests on the idea that some problems stay slow to solve. According to TechCrunch, OpenAI told the researchers it checked and was reasonably confident no crypto systems are broken. That reassurance matters, and it deserves independent confirmation.

I want to be careful here and excited at the same time. A machine-generated result that overturns a durable hypothesis is exactly the kind of useful AI we have argued for: not a chatbot trick, but new knowledge. MIT's Ryan Williams, who is organizing the field's response, described a proof that is partly routine and partly genuinely strange to him, with a few sections he calls alien-looking. That is the signature of something worth taking seriously.

But a claim is not a consensus. Anthropic mathematician Levent Alpöge suggested OpenAI leaned on existing work, and then Anthropic published its own refutation within hours. When two rival labs race to plant flags on the same mountain, we should expect credit fights and competitive pressure to shape how results are presented. Peer review exists so that speed does not substitute for verification.

What encourages me is the process change. Earlier this month Williams called OpenAI's proof drop a denial-of-service attack on mathematicians. This time the computer scientists formed a working group, asked for public proofs, and pushed OpenAI to fund a conference. Russell Impagliazzo and Ramamohan Paturi, who first stated ETH, are part of interpreting it. That is the right model: labs bring the compute, the field keeps custody of the truth.

The harm to name is quieter. If every hard problem a graduate student might cut their teeth on becomes low-hanging fruit for a model, how does the next generation of theorists learn? Williams himself flagged training future scientists as a real concern. Scale this up and we could get a research culture that consumes results it cannot independently produce or check. I'm watching whether the labs invest in that human capacity as aggressively as they invest in the headlines.

Our read: this is likely a genuine milestone, not the last word. Williams doubts OpenAI's algorithm is the best possible, and he says it should nudge, not flip, anyone's bet on P versus NP.

P versus NP asks whether every problem whose answer can be checked quickly can also be solved quickly. Most researchers assume not, and ETH was supporting evidence for that view. A sub-exponential algorithm for the class of puzzles ETH covers would not settle P versus NP, but it weakens one of the intuitions people relied on.