The Exponential Time Hypothesis Fell Twice. The Way Through Was a Minus Sign

On 26 October two papers appeared within hours of each other. One, from OpenAI, is titled The Exponential Time Hypothesis is False. The other, from Anthropic, is credited to “Claude” and titled A 2^o(n) Time Algorithm for 3-SAT. Both say the same thing: the reference hard problem of computer science, which I explain below with a dinner party, can be solved faster than anyone believed possible, and a conjecture that hundreds of results were built on is false. Both come with a proof checked line by line by Lean, a program that verifies mathematics mechanically. Both were found by an AI model the labs have not released. Anthropic’s paper dates its discovery to 16 October, “with 14M output tokens and no human input”; OpenAI’s manuscript is dated 17 October.

The headlines went for the AI-cracks-a-decades-old-puzzle angle and stopped there. That leaves out the part I find most interesting, which is how. I read both papers, and the answer is not two unrelated tricks. Both algorithms run into the same wall that every SAT algorithm since the 1980s has run into, and both get through it the same way: by solving a harder problem than the one asked, and letting negative numbers cancel. One of them does it with an identity a Danish mathematician wrote down in 1818.

None of this makes any real software faster, and none of it settles P vs NP, the famous million-dollar question. I’ll get to why. First, the problem, in plain words, because without it nothing else in this story makes sense.

The problem: a dinner party with conditions

Say you are organising a dinner and your friends have sent conditions. “I’ll come if Ana comes or Bea doesn’t.” “At least one of Carlos and Diego.” “Not Ana, Bea and Carlos all together, please.” Each friend is a yes/no decision, and each condition mentions at most three friends. The question: is there any guest list that meets every condition at once?

That is 3-SAT. “SAT” stands for satisfiability: can all the conditions be satisfied together? The “3” is because each condition, called a clause, involves at most three yes/no variables. Written the way computer scientists write it, a clause looks like $(x_1 \lor \lnot x_2 \lor x_5)$: “friend 1 comes, or friend 2 doesn’t, or friend 5 comes”.

It looks like a parlour puzzle, and it is the puzzle. In 1971 Stephen Cook showed that a huge family of problems (timetables, delivery routes, verifying that a chip has no bugs, Sudoku, and thousands more) can be translated into it. Solve 3-SAT fast and you solve all of them fast. That is why it is the reference hard problem of computer science.

What makes it hard is an asymmetry. If someone hands you a guest list, checking it is trivial: go through the conditions one by one. Finding one is another matter. With $n$ friends there are $2^n$ possible lists: with 30 friends, about a billion; with 100, so many that a million computers each checking a billion lists per second would need some 40 million years to go through them. The question since the 1970s has been how much better than “try them all” you can do.

What the hypothesis said

The best algorithms don’t try everything; they prune, guess cleverly, and backtrack. But their running time still grows exponentially: each extra variable multiplies the work by a fixed factor, the base. For trying everything the base is 2 (one more friend, twice the lists). Schöning’s random walk brought it to $1.334$ in 1999, PPSZ with Hertli’s analysis to $1.308$, Liu’s deterministic algorithm to $1.328$. That sounds like a small gain and it is an enormous one: $2^{100}$ is a 31-digit number, $1.308^{100}$ a 12-digit one. But forty years of very clever work never brought the base close to 1.

In 1999 Russell Impagliazzo and Ramamohan Paturi turned that experience into a conjecture, the Exponential Time Hypothesis (ETH): the base can be lowered but never to 1. Put precisely: there is some number $c$ greater than 1 such that no algorithm solves every 3-SAT instance faster than $c^n$. However clever the algorithm, each extra variable will always cost at least that fixed multiplier. Its stronger sibling, SETH, says that when conditions can mention many variables, you cannot even lower the base much.

Papers usually write the same thing with the base fixed at 2 and the change moved into the exponent. Any base $c$ is a power of 2, $c = 2^{\delta}$, so $c^n = 2^{\delta n}$: trying everything is $\delta = 1$, and $1.308^n$ is about $2^{0.39n}$. Lowering the base towards 1 and lowering $\delta$ towards 0 are the same thing. In that language ETH says $\delta$ can never go below some fixed positive number.

An algorithm that breaks this is called subexponential, written $2^{o(n)}$: its exponent grows more slowly than $\delta n$ for every $\delta > 0$. In the language of bases, the multiplier you pay per extra variable keeps shrinking towards 1 as the problem grows. It is still not fast in any everyday sense, but it is a different kind of growth, and ETH said it was impossible.

That bet was not idle. Anthropic’s paper reports a literature search, carried out by Claude, that found more than 800 papers proving at least one result only under ETH or something that implies it. ETH is the reason we “know” that k-Clique has no $n^{o(k)}$ algorithm, that many parameterized algorithms are optimal, that dynamic programming over tree decompositions cannot be improved. In 2019 Ryan Williams gave two separate estimates: a 70% chance that ETH was true, and a 25% chance that SETH was true. They are not slices of one pie and are not meant to add up to 100%: SETH is the stronger claim (if it holds, ETH holds too), so it can only be the less likely of the two. Most of the field would have put both numbers higher.

Both papers now give a deterministic algorithm that runs in $2^{o(n)}$: for every $\delta > 0$ it is eventually faster than $2^{\delta n}$, which is to say it eventually beats every base above 1. That refutes ETH, SETH, Gap-ETH and the counting version #ETH in one go.

The wall

Here is the intuition for why the base never reached 1, and it is the same picture in both papers.

Go back to the dinner. Draw each condition as a dot, and join two dots with a line when they mention the same friend. Anthropic’s paper says each line “carries bits”, one per shared yes/no decision. The natural shortcut is divide and conquer: split the drawing in two halves, try every possible answer for just the friends whose lines cross the split, and for each of those, solve each half on its own. If your friends form two groups that barely know each other, only a few decisions cross the split, and this is enormously faster than trying every list.

The problem is that you don’t get to choose the friends. Random sets of conditions, and the hard instances generally, look like expander graphs, where every way of splitting the nodes into two halves of comparable size is crossed by a constant fraction of all the edges. In the paper’s words, “any algorithm that fixes one tree of cuts in advance and enumerates the crossing bits of each cut takes time $2^{\Omega(n)}$. Thus earlier divide and conquer ideas only improved the constant in the exponent.”

To go through the wall you have to stop paying for every crossing bit. And there is no way to do that if every quantity you handle means “number of solutions of something”, because counts of solutions are non-negative and cannot cancel.

Count, don’t decide

So both papers do something that sounds backwards. They don’t ask “is there a valid guest list?”. They ask “how many valid guest lists are there?” and compute the exact number, which is the #3-SAT problem and is in principle much harder (the previous best for counting was around $1.64^n$, worse than for deciding). Testing whether the count is zero then decides satisfiability for free.

Why make your life harder? Because a count is a sum, and a sum is algebra. The number of satisfying assignments is

$\#F = \sum_{x \in \{0,1\}^n} \prod_{\text{clauses } e} \Phi_e(x)$

where each $\Phi_e$ is 1 if clause $e$ is satisfied and 0 otherwise. A sum of products can be rearranged, rewritten, expanded and regrouped, and nothing forces the intermediate terms to be 0 or 1 or even positive. Once negative numbers are allowed in the middle of the computation, two expensive pieces can cancel into a cheap one. Branching algorithms, which ask “what if $x_1$ is true?”, can’t do this: every branch is a real sub-question with a real non-negative answer.

Where do negative numbers come from, if every list either works or doesn’t? From subtraction, the same as at school. Take the condition “Ana comes, or Bea doesn’t”. Counting the lists that meet it directly is awkward, because an or ties the two friends together. Count instead all lists, minus the lists that break it. A list breaks it only when Ana stays home and Bea comes, and an and splits cleanly, one friend at a time. With just Ana and Bea there are 4 lists, exactly one of them breaks the condition, so the count is 4 − 1 = 3. In the formula above that is $\Phi = 1 - (1 - x_{\text{Ana}})\,x_{\text{Bea}}$.

Do that for every condition and multiply out, and the count becomes a long sum of simpler terms with plus and minus signs. No single term is the number of valid lists of anything; some are negative; only the total is the count. What you gain is that each term is easy to split into independent pieces. Done naively there are far too many terms, so the work of both papers is in choosing which signed pieces to write, so that the ones linking far-apart parts of the problem cancel.

That is the common move. The two papers then implement it in completely different ways.

If you only want the idea, you have it: the wall is that hard problems can’t be split cleanly, and the way through is to count with numbers that can be negative, so the expensive parts cancel. The next two sections show how each lab did it, with a bit more mathematics; you can skip to What changes, and what doesn’t without losing the thread.

Claude’s route: an identity from 1818

Anthropic’s algorithm stays with the graph picture and attacks the bits that cross.

Take the clause graph and merge clauses into a modest number $K$ of big nodes, so that every pair of big nodes is joined by an edge carrying the same number $\lambda$ of bits. The quantity to beat is the total number of crossing bits, $S$. Now place the nodes on a $g \times g$ grid. Most edges are diagonals: they join two nodes in different rows and different columns. Every diagonal belongs to exactly one rectangle, and each rectangle has two diagonals: the top-left corner holds a string $x$ that must equal the bottom-right’s $v$, and the top-right holds $y$, which must equal the bottom-left’s $u$. That pair of equality checks, $[x = v]\,[y = u]$, the paper calls a crossing.

If you merge each row into one node, a crossing costs 6 bits per block of 3: the top row has to tell the bottom row both $x$ and $y$. Here comes the identity. For blocks of 3 bits there is a sign function $\sigma$ such that

$2\,[x = v]\,[y = u] = [x \oplus y \oplus u \oplus v = 0]\,\big(\sigma(x,y)\,\sigma(v,u) + \sigma(x,u)\,\sigma(v,y)\big)$

and it can be checked by brute force on all 4,096 settings of the 12 bits. Read the right-hand side as two terms. In the first, the row choice, each $\sigma$ depends only on one row, and the two rows only need to agree on the single 3-bit string $x \oplus y = u \oplus v$. That costs 3 bits, half of the 6. The second term, the column choice, is still expensive if you merged rows, but it costs only 3 bits if you merge columns instead. Neither term means anything combinatorially, they take negative values, and only their sum is a count. But each term is cheap in one direction.

The rest is bookkeeping, done carefully. Strings are split into blocks of 3, and the expansion is grouped by how many blocks took the column choice, which keeps the number of terms polynomial. For each term the algorithm merges rows or columns, whichever is cheaper. Per block, the two directions together cost $3 + 6 + 1 + 1 = 11$ bits against the $12$ of two crossings, so the cheaper direction pays at most $11/12$ of what was there before. Then it groups the merged rows into $K$ balanced super-nodes and recurses.

The paper writes the running time as $2^{e S}$, where $S$ is the number of bits on the edges, proportional to the size of the formula. So $e$ plays the role of $\delta$ above, and $2^e$ is the base, paid per bit instead of per variable. One level shrinks $e$ by a factor of $11/12$. Repeat it and $e$ goes to zero, which is the base going to 1: the paper’s bound is $e_\ell \le 1.12\,(11/12)^\ell$. The price is that each level needs vastly more nodes, $K_\ell = 9K_{\ell-1}^{16}$ starting from 64, which is why all of this only matters for astronomically large formulas.

The identity is the beautiful part. Its classical form says that the product of two sums of eight squares is again a sum of eight squares. Ferdinand Degen presented it to the St Petersburg Academy in 1818, and John Graves found it again in 1843 while showing that the norm of the octonions, the eight-dimensional cousin of the complex numbers, is multiplicative. The sign function $\sigma$ in the algorithm is, in the paper’s words, “the table of signs of the multiplication of the octonions, with the basis elements renamed”. Hurwitz proved in 1898 that such identities exist only for 1, 2, 4 and 8 squares. The paper has an appendix explaining why the search for a cheaper decomposition of a crossing leads straight to Hurwitz’s problem, and why, under the simple bit count it uses, only eight leaves a gain: two squares break even, four break even, eight give 11 out of 12.

So the thing that broke ETH is the multiplication table of the octonions, used to cut bits on a grid.

OpenAI’s route: deform the problem, then interpolate back

OpenAI’s algorithm uses the same “count, and let terms cancel” idea through a different door: interpolation.

Start from the same formula for $\#F$. Now introduce a parameter $T$ and replace each variable occurrence inside each clause by a linear combination of variables whose coefficients are polynomials in $T$. At $T = 0$ every replacement is the original variable, so the deformed sum $H(T)$ satisfies $H(0) = \#F$. At the points $T = 1, \dots, Q$, the replacements are designed so that the variables split into small groups that interact only through a few shared “measurements”, small integer linear combinations of each group’s bits. Fix the values of those measurements and the sum factorizes group by group, exactly the way the clustered formula of the earlier figure would. At those points the expensive problem becomes cheap.

Because $H$ is a polynomial of known degree, its values and a few derivatives at the easy points determine it completely, and you read off $H(0)$. Interpolation here is not an approximation: it is exact rational arithmetic. The whole difficulty is in a tension between two costs. The replacements must have low degree in $T$, or you need too many Taylor coefficients per point. And they must respect a different grouping at each of the $Q$ points, which naively costs degree $Q$.

The construction that resolves it is where the minus sign comes back. It is built out of swaps: permutation matrices $\Pi_s$ that exchange two group labels at position $s$, each with eigenvalues $+1$ and $-1$. A basis vector with $j$ of its positions in the $-1$ eigenspace gets multiplied by $(-1)^j$ under the full swap. OpenAI chooses a polynomial $f$ that interpolates $(-1)^j$ only on a short window of $j$ values, centred where a binomial distribution puts almost all of its mass. Inside the window the construction is exact; the few directions outside it are paid for with explicit measurements. The window only needs to be about as wide as the binomial’s standard deviation, $\sqrt{Q}$, and with $Q \approx \log n$ that is where the $\sqrt{\log n}$ in the final bound comes from.

Multiply out the three costs (Taylor data, measurements, one group at a time) and each one is $2^{o(n)}$. The algorithm also runs in polynomial space, which Anthropic’s does not claim.

Same wall, same minus sign

Side by side:

The bounds land in the same place, which is either a coincidence or a hint about where the natural barrier for this family of techniques sits. Neither paper knows how to remove the $\log\log n$ for general formulas.

And the mechanisms rhyme more than they look. OpenAI’s construction is literally built from swap operators with eigenvalues $\pm 1$. Anthropic’s README compresses its own key idea into a paragraph that includes “Per bit, SWAP = I − 2·singlet”, the physicist’s way of writing a swap as the identity minus a signed correction. Both papers solve a harder problem so they can work with signed quantities, and both get their saving from writing an exchange of two things as a combination of cheaper things with signs. The non-negative world, where every intermediate number counts solutions of something, is exactly where ETH was true.

What changes, and what doesn’t

Nothing changes in practice. Anthropic’s paper is unusually blunt about it. For a 3-CNF with $m = 5n$ clauses its bound beats the $2^n$ of brute force only once $n > 10^{10\,000}$, and the bound in $n$ alone only once $n > 10^{10^8}$. The authors add that their general approach “seems unlikely to yield any general improvement unless $n > 10^7$, however it is instantiated”, while brute force is already impossible at $n = 100$. Your SAT solver, your scheduler, your verification tool are exactly as fast as last week.

P vs NP is untouched. P vs NP asks whether problems like 3-SAT can be solved in polynomial time, with work growing like $n^2$ or $n^3$, which is far faster than anything in these papers. ETH was a stronger bet than P ≠ NP, so losing it says nothing about the weaker one. And a $2^{o(n)}$ bound for 3-SAT does not transfer to every NP problem, because polynomial-time reductions can blow up the number of variables polynomially, and $2^{o(n)}$ composed with a polynomial is no longer subexponential. For problems with reductions that keep the size linear, it does transfer: OpenAI derives subexponential counting of independent sets, proper colourings and perfect matchings; Anthropic lists Independent Set, Clique, Vertex Cover and Dominating Set in $O(2^{\delta n})$ for every $\delta > 0$.

A shelf of theorems changed status. Everything proved “under ETH” or “under SETH” has lost its hypothesis. Some of it survives on weaker foundations: the quadratic lower bounds for edit distance and longest common subsequence also follow from the Orthogonal Vectors conjecture, which neither paper refutes. Much of it, the 800-odd papers’ worth, now needs a new reason to be true or turns out to be false.

And there is one genuinely unconditional gain. Through Ryan Williams’s programme, which turns slightly-faster-than-brute-force SAT algorithms into circuit lower bounds, both papers get that the class $E^{NP}$ has no Boolean circuits of linear size. OpenAI’s version gives a lower bound of order $n\sqrt{\log n}$. The best known before, over the full binary basis, was $3.1n$. Circuit lower bounds are one of the most stuck areas of complexity theory, and this one came out as a side effect.

What Lean checks, and what it doesn’t

Both results are formalized, and both teams are careful about what that means. Anthropic’s README says it in one line I wish every formalization carried: “Lean checks the proofs, but no machine checks that this file says what the paper says; the file is kept short so that a reader can check this.” OpenAI’s Lean scope note is similarly precise: the machine-checked bound is the weaker one with $(\log\log n)^2$; the sharper bound in the paper is not.

That is the gap I wrote about in Proved, Certified, Swept, Sampled: a green check is a statement about a specific claim, and the work is knowing which claim. Here it is handled well. The statements are short, they are printed in the papers, and the differences from the prose are listed. As I write this, human review is still under way: according to the coverage, OpenAI handed its result to outside reviewers that include Impagliazzo and Paturi themselves. A Lean proof of a correctly stated theorem leaves them very little to find, but “correctly stated” is the part they are there for.

The proof that fits in a prompt

One more detail, and for someone who builds with these models it is the one that stays with me. At the end of Anthropic’s README there is a section titled “The key idea, in condensed form interpretable by AI models”. It is a single paragraph. It starts “The exponential time hypothesis is false!”, states a recursion for the cost of contracting tensor networks on a complete graph, mentions the grid, the swap, the grouping by number of singlets, and ends “Prove it.” The README says that Claude Opus 5.5 at high effort can rederive the refutation, in its weaker $O(2^{\delta n})$ form, from that paragraph alone.

That is a new kind of mathematical object. For centuries a proof has been written for a human reader, at whatever level of detail that reader needs. Here there are three layers: a 49-page paper for people, a Lean development for the kernel, and a one-paragraph hint for a model, which is enough because the model can fill in the rest. When I wrote about the Navier–Stokes blow-up, the bottleneck was the opposite one: the machine’s drafts were close to unreadable, and turning them into a paper a person could follow was weeks of work. Seven weeks later, the most compressed description of a major result is the one written for a machine.

What to take from it

• ETH is false, twice, independently, with formal proofs, pending the human review that is now under way. SETH, Gap-ETH and #ETH go with it.
• The wall was the expander, and the way through was a minus sign. Both algorithms count instead of decide, so that terms can be negative and cancel. That is the one-sentence intuition, and it is the same for both.
• Claude’s version runs on the octonions. A 1818 identity for sums of eight squares turns two crossing equality checks into terms that are each cheap in one direction, and a recursion multiplies the exponent by 11/12 per level until it is as small as you like.
• OpenAI’s version deforms and interpolates. A polynomial that equals the count at 0 and splits into independent groups at $1, \dots, Q$, held together by swap matrices and a polynomial that imitates $(-1)^j$ on a window under a bell curve.
• No practical consequence. The crossover is beyond $10^{10\,000}$ variables. The consequences are for theory: hundreds of conditional lower bounds lose their hypothesis, and a circuit lower bound moved for free.
• Two labs, the same week, the same bound. Whatever this says about the problem, it says something about the models: the frontier of what they can find now includes a result that one of the field’s leading experts, in 2019, put at 70-to-30 against.

---

Sources: Anthropic’s paper and Lean formalization (A 2^o(n) Time Algorithm for 3-SAT, by Claude), OpenAI’s Lean scope note and paper (The Exponential Time Hypothesis is False).

On the eight-square identity and the octonions: John C. Baez, “The Octonions”, Bulletin of the AMS 39 (2002), 145–205; J. H. Conway and D. A. Smith, “On Quaternions and Octonions”, A K Peters, 2003; A. Hurwitz, “Über die Composition der quadratischen Formen von beliebig vielen Variabeln”, Nachr. Ges. Wiss. Göttingen (1898), 309–316; and Degen’s eight-square identity on Wikipedia.