A $2^{o(n)}$ Time Algorithm for 3-SAT
We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in $2^{o(n)}$ time. Our algorithm in fact solves the harder problem #3-SAT, providing a count of the number of satisfying assignments. The result was discovered by an internal research Claude model and has been formalized in Lean 4.
Comments and reviews
No comments yet.
Discussed elsewhere
Throughout this post I will assume that the recent results by OpenAI and Anthropic contain correct proofs of what they claim.) I wrote the following about 2 years ago but did not post it. It's dated, but that's the point. BEGIN DOCUMENT FROM TWO YEARS AGO Why do we think \(P\ne NP\)? a) Lots of…
The results resolve major problems in math, physics and computer science. But like other recent AI-generated “slop drops,” the releases are already controversial
— Ryan O'Donnell (@BooleanAnalysis) Oct 29, 2026
The counting variant (#PPM) of the permutation pattern matching (PPM) problem asks for the number of occurrences of a permutation pattern in a host permutation of length $n$. The problem admits faster algorithms than the trivial $O^*(2^n)$ time enumeration; the best known running time, for both…
The October 2026 refutations of the Exponential Time Hypothesis count satisfying assignments in time $2^{o(n)}$, but an asymptotic bound does not say from which input size, the crossover point, they beat the best known algorithms. We make the #3-SAT recursion of Anthropic's algorithm explicit and…
API
curl /api/v1/records/hexagon/2610.00577
curl -X POST /api/v1/records/hexagon/2610.00577/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00577/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
The Exponential Time Refutationblog.computationalcomplexity.orgLance Fortnow
In this week's big news (though it's only Wednesday), OpenAI announced a proof that the exponential-time hypothesis is false , with a Lean proof . Later Anthropic released their own paper . Ryan O'Donnell and Shiva Kintali posted follow-up proofs, smartly focusing on simplicity rather than getting…