Explainers

AI Refuted the Exponential Time Hypothesis. Why Nothing Gets Faster

OpenAI and Anthropic say their AI models refuted the Exponential Time Hypothesis. I believe the proof, but its speedup starts past 10^10,000 variables.

MesmerTools•November 15, 2026•4 min

On October 26, 2026, OpenAI and Anthropic each published an algorithm that solves 3-SAT, the standard hard problem, faster than exponential time. The Exponential Time Hypothesis (ETH), a 1999 idea that more than 800 papers lean on by Anthropic's count, said that couldn't happen. Both labs say their AI models found it on the same day.

I read both papers and ran the numbers, and I'd believe the theorem and ignore the speedup. Anthropic's proven bound doesn't beat brute force until a formula passes 1010,000 variables, so nothing you run gets faster and P vs NP hasn't moved.

A dark stone column carved with ETH 1999, split by a diagonal crack leaking amber light, beside the headline Pillar falls. Nothing gets faster.

Nobody has refereed the proofs, and I still believe them

Neither paper has been peer reviewed as of November 2026, and Anthropic's says its formal proof "was written by AI models and reviewed by other instances of the same models; at the time of writing no person is known to have checked it."

That sounds alarming until you look at what it's written in. Both labs shipped proofs in Lean, where a small program called a kernel checks every logical step, and I haven't seen a reported error.

But a kernel can't tell you whether the statement means what the paper claims, so a person still has to read that part, a couple of hundred lines. What I stand on is that two labs got there separately, and outsiders who ran the Lean proofs say they compile.

A hypothetical of mine: swap the 3 for a 2 and the kernel is just as happy, which is why the small slab still needs a person.

So the Exponential Time Hypothesis is false

3-SAT asks whether n on/off switches can be set to satisfy rules that each constrain three of them. Trying all 2n settings of 100 switches, at a billion a second, takes 40 trillion years. The best older method, 1.307n, takes seven minutes.

ETH said that base, the number raised to the power n, has a floor above 1. The new bounds have none. I worked out what OpenAI's simple recipe costs from its inequalities.

Every new bar beats the old record, but read the n it needs; this is my calculation of a bound, not a runtime.

OpenAI's recipe splits the switches into small rooms and rewrites the rules until rooms see each other only through a few shared numbers, the dials. Fix the dials and each room can be counted alone. The rewrite distorts the rules, so it counts at several settings of a blur knob and works back.

A toy with 24 switches and a hand-picked formula: once the crossing rules become dials, each room runs through its 64 settings alone.

But you can't just keep adding rooms

If rooms save that much, why not use more of them? A bookkeeping table has to fit inside the formula, so rooms and blur settings share one budget, and the budget is log n, roughly the number of digits in n.

I ran the recipe's inequalities, tuned in its favor. At 1010,000 variables it still loses to brute force, and it first wins near 10240,000.

More rooms shrink the amber block until the dials burst through the top; my calculation, tuned in the recipe's favor.

Anthropic's bound gets there far sooner, at 1010,000 with five rules per variable. Here's how far that still is.

Seventy-eight powers of ten get you to the atoms in the universe, and the number the exponent divides by only crawls from 2.6 to 16.

So nothing you run gets faster

For anything you run today, I wouldn't change a thing. ETH only covers the worst possible formula, and the SAT solvers developers use handle real ones with millions of variables.

What I don't know is where the algorithm really starts to win. Those thresholds are proven bounds, and Anthropic's paper says its approach seems unlikely to help below ten million variables, so the true crossover is somewhere in that gap.

More from the Blog