Hours after OpenAI, Anthropic announced that its Claude model had also disproved the exponential time hypothesis (the claim that every algorithm for 3-SAT requires an exponentially growing number of steps)

Hours after OpenAI, Anthropic announced that its Claude model had also disproved the exponential time hypothesis (the claim that every algorithm for 3-SAT requires an exponentially growing number of steps)

On October 27, Anthropic published a paper and a proof in Lean, a program for checking mathematical proofs by computer. Claude is listed as the author: according to the company, its internal model found the main algorithm on October 16 without human involvement.

The exponential time hypothesis (ETH) concerns the 3-SAT problem: assign “true” or “false” to n variables so that every clause of the form “x or not y or z” is satisfied. Exhaustive search takes about 2^n steps, and ETH states that, for some c > 0, every algorithm requires at least 2^(cn) steps in the worst case. For any δ > 0, Claude’s algorithm counts all satisfying assignments in time on the order of 2^(δn); when δ is smaller than c, this is faster than the ETH bound. By Claude’s count, more than 800 papers prove at least one result conditional on ETH or a stronger hypothesis.

The set of clauses (the formula) is converted into a graph: each clause becomes a vertex, and variables shared by two clauses form a connection. The paper calls the number of shared variables the number of connection bits. Once the graph is split into two parts, it is enough to enumerate the values of the connecting variables (each bit doubles the number of possibilities) and count the satisfying assignments in each part separately. For random formulas, however, any split into roughly equal parts cuts through on the order of n bits, so the enumeration remains exponential.

To reduce the number of bits crossing a cut, Claude rewrites the expression for the number of satisfying assignments. Clauses are grouped and arranged in cells on a grid: two rows and two columns define a rectangle, whose diagonals connect opposite corners. Suppose each diagonal carries 3 bits, for a total of 6. The eight-square identity replaces this pair with a shared constraint on the four corners and a sum of two alternatives: connections along the rows or along the columns. If each row is merged into a single vertex, connections along rows become internal to the vertices: the “along rows” alternative costs 3 bits, while the “along columns” alternative still costs 6. Merging columns reverses these costs. For each combination of alternatives across the rectangles, either rows or columns are merged, whichever costs less, giving an average of at most 4,5 bits per rectangle instead of 6. The full algorithm repeats this procedure, with each pass leaving about 11/12 of the bits. A number of passes that depends only on δ is enough to achieve a running time of 2^(δn). A more refined construction in place of the identity yields the final bound of 2^(O(n·log log n/√log n)).

Carl Ferdinand Degen discovered the identity in 1818, and John Graves rediscovered it in 1843 while studying octonions, eight-dimensional numbers. Jelani Nelson, an Anthropic employee, wrote on X about replacing the pair of connections: “This replacement comes from the so-called ‘eight-square identity’; it is related to octonions, which I still know nothing about :)”.

The final bound, which depends only on n, beats exhaustive search only when n exceeds 10^(10^8), a one followed by one hundred million zeros.

According to the paper, the Lean 4 proof was accepted by two independent proof checkers, the Lean kernel and nanoda. Only a human can check whether the formal statements of “ETH is false” and the main theorem capture their intended meaning. AI models wrote the code, and other instances of those models checked it: “at the time of writing, no human is known to have reviewed it”.

OpenAI gives the discovery date as the same October 16, while Anthropic writes that OpenAI’s model “independently and simultaneously” reported a similar result. The method in OpenAI’s manuscript is different: it uses an algebraic approach based on polynomials, while Anthropic’s approach arranges the graph on a grid.