AI just cracked a 25-year-old conjecture. To get why, start with P vs NP.
An AI model just disproved a hypothesis that complexity theorists had been building on since 1999. On October 25, OpenAI posted a 67-page preprint titled "The Exponential Time Hypothesis is False", found by an internal model and partly checked in the Lean proof checker. Anthropic soon posted a refu
Posted on Oct 31 • Originally published at smiit.in
An AI model just disproved a hypothesis that complexity theorists had been building on since 1999.
On October 25, OpenAI posted a 67-page preprint titled "The Exponential Time Hypothesis is False", found by an internal model and partly checked in the Lean proof checker. Anthropic soon posted a refutation of its own. Lance Fortnow: "it is safe to assume now that the exponential-time hypothesis is toast."
Some coverage said P vs NP was about to fall, or encryption was about to break. To see what actually changed, start with P vs NP.
(a ∨ b ∨ c) ∧ (¬a ∨ d ∨ e) ∧ (¬c ∨ f ∨ g) Enter fullscreen mode Exit fullscreen mode ∨ is OR, ∧ is AND, ¬ is NOT. Set each letter true or false so every bracket has a true part. That's 3-SAT.
Checking an answer takes one pass. Finding one means searching 2ⁿ assignments: about a quadrillion at 50 variables. The best algorithm before October, PPSZ, gets that to about 1.307ⁿ. Faster, still exponential.
The full version has a live puzzle you can solve by hand before brute force grinds through it. Read more and try it here.
"Fast" means polynomial time, steps growing like n² or n³. P is problems you can solve that fast: sorting, shortest paths. NP is problems where an answer can be checked that fast: 3-SAT, big Sudokus, exam scheduling.
Is everything easy to check also easy to solve? That's P vs NP, with a million-dollar prize since 2000. Most researchers think no. Nobody has proved it.
In 1971 Stephen Cook showed every NP problem translates into SAT in polynomial time. Problems everything in NP reduces to are NP-hard, and if they're in NP too, NP-complete. A fast algorithm for any one of them makes all of NP fast.
Between polynomial and exponential there's a middle zone, like 2^√n, called sub-exponential. In 1999 Russell Impagliazzo and Ramamohan Paturi bet 3-SAT can't get there: for some fixed δ > 0, it needs 2^(δn) time. That's ETH.
The logic runs one way. ETH true means P ≠ NP. ETH false says nothing about P = NP.
Lots of results said "no algorithm for X beats this, assuming ETH". Fortnow: "The fact that ETH and SETH fail doesn't mean their implications are false." They just need a new foundation.
A deterministic algorithm that counts every satisfying assignment in:
(n+m)^O(1) · 2^( n / (log n)^(1/2 + o(1)) ) Enter fullscreen mode Exit fullscreen mode The exponent is n divided by about √log n, and that divisor keeps growing, so eventually this beats 2^(δn) for any δ. That's what ETH ruled out.
Watch the brackets. "2ⁿ divided by √log n" would barely beat brute force (about 2^998.6 at n = 1,000). The real bound puts the division inside the exponent: about 2^380.
Impagliazzo, Paturi and MIT's Ryan Williams are reviewing it. Fortnow notes the Lean proof gives "a slightly weaker bound". It isn't peer reviewed yet.
The paper hides its constants, and the new curve only beats PPSZ once √log n outgrows them.
My illustration: with C = 1 it wins from about 820 variables. With C = 6, you'd need more variables than atoms in the universe. It's a "galactic" algorithm, and nobody will ever run it.
Reductions to 3-SAT inflate the size. Turn n items into n² variables and the gain is gone.
The paper says the result "does not imply that general NP problems admit subexponential time algorithms". Fortnow: "It gives nothing new for Subset Sum or Traveling Salesman."
No. Sub-exponential time for all of NP would need 3-SAT in 2^(n^o(1)), and this is nowhere near. Williams still says people should "put a little more weight on the plausibility of P = NP, but one's weight may vary."
RSA rests on factoring, which isn't believed to be NP-complete and already has a sub-exponential algorithm, the number field sieve. Encoding it as SAT is the losing case above. Williams asked OpenAI whether it breaks any cryptosystem, and they said they're reasonably confident it doesn't.
If someone pushes 3-SAT to 2^(n^o(1)), every NP problem goes sub-exponential and this gets much louder. Until then, one of the safest bets in computer science lost, and it lost to a machine.
Did you expect ETH to fall before P vs NP got any closer? Tell me in the comments.