How Big Is Too Big
Two AI labs say 3-SAT can be solved faster than the Exponential Time Hypothesis allowed. Here is how fast the problem grows, where the new bound would finally win, and what falls if the hypothesis does.
1 · Add variables
A 3-SAT formula with n true-or-false variables has 2n possible settings. Move the slider and compare checking them all with the best algorithm known before October, at a billion steps a second.
Steps, not real programs: constant factors and polynomial costs are ignored. The 1.308n record is for randomized algorithms; the deterministic record was 1.328n. Both are cited in Anthropic’s paper.
2 · Where does the new bound win?
The new algorithms grow more slowly than any exponential — eventually. Anthropic’s paper says when. Each bar shows how many digits the number of variables would have, on a log scale.
Thresholds from Anthropic’s paper, “A 2o(n) Time Algorithm for 3-SAT”: brute force is impractical by n = 100; its approach seems unlikely to help below n = 107; its bound beats exhaustive search only past 1010,000 variables for formulas with 5n clauses, and past 10108 in general.
3 · Switch off a hypothesis
Hypotheses rest on each other. If one is false, everything that implies it is false too — and nothing else. Press the button and see which ones fall with ETH.
Arrows mean “implies.” SETH and Gap-ETH each imply ETH, so refuting ETH refutes them. SETH also implies the Orthogonal Vectors hypothesis, but refuting SETH does not refute OV — Anthropic’s paper says its result leaves OV standing. #ETH (counting) and NSETH fall because the algorithms count solutions directly, as OpenAI’s paper states. Anthropic counted more than 800 papers with a result that rests only on ETH or a hypothesis implying it.
4 · Two labs, one day
| OpenAI | Anthropic | |
|---|---|---|
| Found | October 16 (internal model) | October 16 (internal Claude model, 14M output tokens, no human input) |
| Paper | “The Exponential Time Hypothesis is False,” 67 pages, dated Oct 17, revised Oct 25 | “A 2o(n) Time Algorithm for 3-SAT,” 49 pages, dated Oct 26 |
| Released | October 26 | October 27 |
| Machine check | Lean 4, on GitHub | Lean 4, re-checked by a second independent kernel |
| People | Impagliazzo, Paturi and Williams lead the examination: “not certification” | Says plainly: “no machine checks that this file says what the paper says” |