writing
On October 25, OpenAI put a 67-page PDF on GitHub with a blunt title: “The Exponential Time Hypothesis is False.” The author line says only “OpenAI”. The proof came out of one of its internal models, and a version of it was checked in Lean, a program that verifies proofs step by step. Anthropic soon posted a refutation of its own. Lance Fortnow, one of the best-known names in complexity theory, wrote on his blog: “I have not verified the proof myself, but 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. The Exponential Time Hypothesis (ETH from here on) is a bet about how hard one puzzle is, and researchers had been building on it since 1999. To see why losing it matters, and why the million-dollar question is still open, you have to start with P vs NP. You need to know what an algorithm is, and that’s about it.
A puzzle that’s quick to check and slow to solve
Here’s a small rule set:
∨ means OR, ∧ means AND, ¬ means NOT. Each group in brackets is a clause. Your job is to set every letter to true or false so that each clause has at least one true part. With three parts per clause, this is called 3-SAT, short for 3-satisfiability.
If someone hands you an answer, checking it is quick. You read each clause once and you’re done. Finding an answer is another story. With n variables there are 2n ways to set them: 1,024 for 10 variables, about a quadrillion for 50, and more than there are atoms in the observable universe once you pass about 270.
Demo 1: check it, then find it
Click variables to flip them and watch clauses light up. When you give up, press "Brute force" and see how many guesses it takes. Then add variables and do it again.
Puzzles are random, with about 4.2 clauses per variable (the range where random 3-SAT tends to be hardest) and a hidden solution planted so there's always an answer. Brute force here tries assignments in counting order.
Smarter algorithms beat trying everything, but they don’t change the shape of the curve. The best one known before October, a randomized method called PPSZ (after Paturi, Pudlák, Saks and Zane), runs in about 1.307n steps. That’s far better than 2n. It’s still exponential: each extra variable multiplies the work by about 1.3.
P is what we can solve fast. NP is what we can check fast.
“Fast” has a specific meaning here: polynomial time. The number of steps grows like a power of the input size, n² or n³ or n10. Double the input and the work grows by a fixed factor. Exponential time, like 2n, is the opposite: add one to the input and the work doubles.
- P is the set of problems you can solve in polynomial time. Sorting, shortest paths, checking whether a number is prime.
- NP is the set of problems where a proposed answer can be checked in polynomial time. 3-SAT is in NP. So is Sudoku (on big n²×n² grids), packing a truck, or scheduling exams so nobody has two at once.
Every problem in P is also in NP. If you can solve it fast, you can check an answer by solving it yourself. The question is whether it works the other way: is every problem that’s easy to check also easy to solve? That’s P vs NP. The Clay Mathematics Institute has offered a million dollars for an answer since 2000. Most researchers believe P ≠ NP. Nobody has proved it.
NP stands for “nondeterministic polynomial time”, not “not polynomial”. It’s a common mix-up, and it matters, because P sits inside NP.
One problem speaks for thousands
In 1971 Stephen Cook proved something that makes SAT special (Leonid Levin found it independently). Every problem in NP can be translated into a SAT formula, and the translation itself only takes polynomial time. Solve the formula and you’ve solved the original problem.
Sudoku shows how. Make a variable for every “cell (row, column) holds digit d”, then add clauses for the rules: one digit per cell, no repeats in a row, column or box. Any satisfying assignment is a filled grid. This kind of translation is called a reduction.
Problems that everything in NP reduces to are called NP-hard: at least as hard as anything in NP. If an NP-hard problem is itself in NP, it’s NP-complete. Thousands of problems are known to be NP-complete, and they all reduce to each other. So a polynomial algorithm for any one of them gives one for all of NP, and that would mean P = NP.
Demo 2: the map of problems
Click a dot to see where a problem lives and why. Then switch to the P = NP world and watch the map collapse.
Click a dot.
A sketch, not to scale. In the P = NP world, P, NP and NP-complete become the same set (apart from two trivial problems that technically can't be NP-complete). Factoring isn't known to be NP-complete, and most researchers think it isn't.
Polynomial grows. Exponential explodes.
It’s easy to nod along at “exponential” without feeling it. Put the curves next to each other and give them a real computer.
Demo 3: the growth race
Drag the slider. Watch n³ stay polite while 2ⁿ blows past the age of the universe. Keep going to see where the sub-exponential curve overtakes PPSZ.
Bar length is the number of digits in the step count (a log scale). Times assume a billion steps per second. All constant factors are set to 1, which real algorithms don't have, so read this for shape, not for timings. The sub-exponential row uses 2^(n/√ln n), the simple form of the new bound.
At 50 variables brute force takes about two weeks. At 100 it’s tens of trillions of years. n³ at 1,000 variables is one second.
ETH is a bet on how hard 3-SAT really is
P ≠ NP only says 3-SAT has no polynomial algorithm. That leaves a lot of room in between. A running time like 2√n is slower than any polynomial but faster than any cn with a fixed c greater than 1. Running times in that middle zone are called sub-exponential.
In 1999 Russell Impagliazzo and Ramamohan Paturi proposed a stronger bet. There’s some fixed δ greater than zero such that 3-SAT can’t be solved in 2δn time. In other words, no sub-exponential algorithm, ever. That’s the Exponential Time Hypothesis. They also proposed a stronger version, SETH (Strong ETH), which says that as clauses get longer you can’t beat 2n by any constant fraction in the exponent.
The logic only runs one way, and this is the part to hold onto:
ETH mattered because people built on it. A whole style of result reads “problem X has no algorithm faster than this, assuming ETH”, and those results told researchers when to stop looking. Fortnow: “The fact that ETH and SETH fail doesn’t mean their implications are false.” They’ve just lost the floor they were standing on.
What the AI actually proved
The paper gives a deterministic algorithm (no coin flips, unlike PPSZ) that counts every satisfying assignment exactly, using polynomial memory. A count above zero answers the yes/no question for free. The running time, for n variables and m clauses:
The first part is ordinary polynomial overhead. The exponent in the second part is n divided by roughly √log n, and that divisor keeps growing. Pick any δ, 0.1 or 0.001, and for large enough n this beats 2δn. ETH said no algorithm could.
Watch the brackets. “2n divided by √log n” would be a much weaker claim: at n = 1,000 it’s still about 2998.6, barely better than brute force. The real bound, with the division inside the exponent, is about 2380, constants ignored.
Impagliazzo, Paturi and MIT’s Ryan Williams are now verifying it for OpenAI. Fortnow notes the Lean proof gives “a slightly weaker bound”, still sub-exponential, and Ryan O’Donnell and Shiva Kintali have posted simpler follow-up proofs. Williams told TechCrunch there are “two or three alien-looking parts”. It isn’t peer reviewed yet.
Sub-exponential doesn’t mean fast
The O(1) and o(1) hide constants the paper doesn’t spell out. The new curve only beats PPSZ once √log n outgrows them, and √log n grows painfully slowly.
Demo 4: the hidden constant
Slide the hidden constant C up from 1 and watch how far out the crossover point runs.
My illustration, not numbers from the paper. It compares 2^(0.386·n), which is 1.307ⁿ, with 2^(C·n/√ln n) and ignores the polynomial factors in front of both. The crossover is where C/√ln n drops below 0.386, so n = exp((C/0.386)²). The real constants are unknown.
With C = 1 the new algorithm wins from a few hundred variables. With C = 2 you need hundreds of billions. With C = 6 you need about 10105, more variables than there are atoms in the universe. It’s a “galactic” algorithm: it settles a question about growth, and nobody will run it. Real SAT solvers, the ones in chip verification and package managers, use different tricks and aren’t affected.
Why it doesn’t spread to every NP problem
Every NP-complete problem reduces to 3-SAT, so doesn’t this speed them all up? Only if the translation keeps the size close, and usually it doesn’t. Turning n things into n² variables wipes out the gain.
Demo 5: what a reduction costs
Pick how much a reduction inflates the problem, then drag the size. Watch the cost per original item: falling means you kept the speedup, climbing means you lost it.
Constants set to 1, using 2^(N/√ln N) for the 3-SAT step on N variables. Compared with brute force on the original problem, 2ⁿ. Even the linear reduction loses to brute force until n is in the thousands, then wins forever after.
The paper says its result “does not imply that general NP problems admit subexponential time algorithms.” Fortnow: “It gives nothing new for Subset Sum or Traveling Salesman.” Problems with tight, linear-size reductions do benefit, like counting graph colorings and perfect matchings.
So, is P = NP now?
No. Even sub-exponential algorithms for all of NP would need 3-SAT in 2no(1) time, something like 2n0.01. The new bound is nowhere close, and polynomial is further still.
It does nudge the odds. Williams: “Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one’s weight may vary.” An assumption most of the field was comfortable with turned out wrong, and that’s a reason to hold the others more loosely.
What about encryption?
RSA rests on factoring, which isn’t believed to be NP-complete and already has a sub-exponential algorithm. The general number field sieve dates to the 1990s, and it’s why RSA keys are 2,048 bits and not 200.
You could encode factoring as SAT, but a multiplier circuit has far more gates than the number has bits, which is one of Demo 5’s losing cases. Williams asked OpenAI whether the result breaks any cryptosystem, and OpenAI said it was reasonably confident it doesn’t. SHA-256 and AES aren’t built on 3-SAT at all. A practical proof that P = NP would be a different story. That isn’t what happened in October.
What this post can’t tell you
- Whether the proof is right. I’ve read the abstract, main theorem and discussion, not all 67 pages. The review is ongoing.
- How fast it really is. The constants are hidden. Demo 4 shows a range, not an answer.
- Who found what. Anthropic’s Levent Alpöge suggested OpenAI built on existing work.
- Which ETH-based results survive. Each one now needs a new reason.
The bet to watch next
Williams: “I don’t think that OpenAI’s algorithm could possibly be the best algorithm you can get.” If someone pushes 3-SAT down to 2no(1), every problem in NP goes sub-exponential, and the P vs NP conversation gets much louder. Until then, the million dollars stays put. One of the safest-looking bets in computer science lost, and it lost to a machine.
Sources
- OpenAI, “The Exponential Time Hypothesis is False” (preprint, 17 Oct 2026, revised 25 Oct 2026): github.com/openai/math
- OpenAI, “Working with academic communities to build scientific understanding”: openai.com
- Lance Fortnow, “The Exponential-Time Refutation”, Computational Complexity blog, 28 Oct 2026: blog.computationalcomplexity.org
- Tim Fernholz, “Frontier AI labs say their models refuted the exponential time hypothesis. What does that mean?”, TechCrunch, 27 Oct 2026: techcrunch.com
- John D. Cook, “ETH is false”, 27 Oct 2026 (links Anthropic’s paper and Kintali’s simplified proof): johndcook.com
- Anthropic’s refutation: hexagonmath.org/2610.00577v1
- Shiva Kintali, “A simplified proof of ETH is false”: shivakintali.github.io
- Impagliazzo and Paturi, “On the Complexity of k-SAT” (CCC 1999, JCSS 2001): cseweb.ucsd.edu
- Hansen, Kaplan, Zamir and Zwick, “Faster k-SAT algorithms using biased-PPSZ” (STOC 2019): arxiv.org/abs/1812.03594
- Clay Mathematics Institute, P vs NP: claymath.org
- Cook-Levin theorem: Wikipedia · NP-completeness: Wikipedia · Exponential time hypothesis: Wikipedia
- General number field sieve: Wikipedia · Sudoku is NP-complete (Yato and Seta, 2003): Wikipedia
All demo values are computed live in your browser. The constants in Demos 3 to 5 are set to 1, which real algorithms don’t have.