{"id":"hexagon/2610.00577","pdf":"https://hexagonmath.org/pdf/2610.00577v1","url":"https://hexagonmath.org/abs/2610.00577v1","tags":["msc:68Q25","msc:68W40","msc:68Q17"],"score":0,"title":"A $2^{o(n)}$ Time Algorithm for 3-SAT","domain":"cs.CC","origin":"ai-generated","source":"hexagon","authors":["Anthropic"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":6,"published":"2026-10-27","reactions":{},"withdrawn":false,"authorship":"no-human-author-claimed","discussion":[{"url":"https://blog.computationalcomplexity.org/2026/10/the-exponential-time-refutation.html#:~:text=In%20this%20week%27s%20big%20news","kind":"web","site":"blog.computationalcomplexity.org","text":"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…","added":"2026-11-03","title":"The Exponential Time Refutation","author":"Lance Fortnow"},{"url":"https://blog.computationalcomplexity.org/2026/11/3sum-and-apsp-and-eth-oh-my.html#:~:text=Throughout%20this%20post%20I%20will%20assume%20that%20the%20recent%20results%20by%20OpenAI%20and%20Anthropic","kind":"web","site":"blog.computationalcomplexity.org","text":"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…","added":"2026-11-03","title":"3SUM and APSP and ETH, Oh My!","author":"Bill Gasarch"},{"url":"https://www.scientificamerican.com/article/dueling-proofs-from-openai-and-anthropic-astound-scientists/","kind":"web","site":"Scientific American","text":"The results resolve major problems in math, physics and computer science. But like other recent AI-generated “slop drops,” the releases are already controversial","added":"2026-11-03","title":"Dueling proofs from OpenAI and Anthropic astound scientists","author":"Joseph Howlett, Peter Hall"},{"url":"https://x.com/BooleanAnalysis/status/2115876059673440339","date":"2026-10-29","kind":"x","added":"2026-11-03","author":"Ryan O'Donnell","handle":"BooleanAnalysis"},{"url":"https://arxiv.org/abs/2610.41048","date":"2026-10-29","kind":"web","site":"arXiv.org","text":"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…","added":"2026-11-04","title":"Faster #PPM from faster #3SAT","author":"László Kozma"},{"url":"https://arxiv.org/abs/2610.41622","date":"2026-10-30","kind":"web","site":"arXiv.org","text":"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…","added":"2026-11-04","title":"Lowered crossover points of Anthropic's subexponential 3-SAT algorithm","author":"Ruhollah Majdoddin"}],"formalized":false,"human_understanding":"some"}