I didn’t get what “ETH is false” meant either.So let’s flip some switches.
OpenAI reports that one of its systems refuted the Exponential Time Hypothesis. ETH for short.
Computer scientists have leaned on ETH for decades. Hundreds of papers say, roughly, “this can’t be done much faster, assuming ETH.” I wanted to know what would actually break if it’s false. This is what I figured out. About two minutes, no math needed.
it’s a claim. people arechecking it right now.
Six switches. Three rules.
Here’s a tiny puzzle. Every rule says the same thing: at least one of these three switches has to be on.
← go on, flip some. ↑(they click)
the ones you’ve tried get scribbled in.
Every new switch doubles everything.
Each switch splits every path in two: off to the left, on to the right. Drag the slider and watch the tree get out of hand.
ways to set them:
Checking one setting against the rules: basically instant. Checking all of them, at a billion a second: 64 ns.
Checking an answer is easy.
Finding one can be another story.
Surely we can skip some?
Yep. If switches 1, 2 and 3 are all off, rule 1 is already broken. Nothing further down that branch can fix it, so you snip it without looking.
Brute force looks at 64 of 64. With shortcuts: press the button.
People have been inventing cleverer shortcuts for decades. For 3-SAT, the standard version of this puzzle, they got from 2n down to roughly 1.3n. That’s a huge win. At 100 switches it’s about 1.3 × 10³⁰ steps versus about 4 × 10¹¹.
but still exponential. every newswitch still multiplies the work.
ETH never said you had to try everything. It said even the best shortcuts couldn’t escape exponential growth in the worst case.
← that’s it. that’s thewhole hypothesis.
What if we stopped searching the tree?
This is the bit that surprised me. Sometimes you can count the answers without listing them. Four switches, two pairs, one rule per pair.
A speed limit challenged. Not every problem solved.
ETH said there’s a floor. However clever you get, the work per switch never shrinks toward zero.
The claimed algorithm’s work per switch keeps sinking. Slowly. Really slowly. But with no floor.
What’s claimed
- A deterministic algorithm that exactly counts the solutions of any k-CNF formula (which also answers 3-SAT), in worst-case time about
2^(n / (log n)^(½+o(1))), using only polynomial memory. - That’s subexponential: it grows slower than
2^(cn)for every c > 0. ETH said that was impossible. - OpenAI reports it was formalized in Lean. Their scope note says the Lean proof covers a slightly weaker bound, still subexponential.
What’s not
- Not P = NP. Subexponential is still far slower than polynomial.
- Not a fast new SAT solver. In OpenAI’s words, practical improvements “will require significant further research.”
- Not every hard problem. The paper itself says this doesn’t give every NP problem a subexponential algorithm.
Where it stands
Independent scrutiny is underway, organized by Russell Impagliazzo and Ramamohan Paturi (who proposed ETH with Francis Zane) and Ryan Williams.
“Our involvement should not be taken as certification of the claim.”
So why does it matter? Hundreds of results say “this can’t be done much faster, assuming ETH.” If the refutation holds up, those results lose their footing, and the hunt for faster algorithms is open again.
If it doesn’t hold up, at least now we both know what ETH means.
Rosh