CS Paper Radar

Lowered crossover points of Anthropic's subexponential 3-SAT algorithm

Ruhollah Majdoddin

cs.CC cs.DS ·submitted 2026-10-30 11:58 UTC · v1
theorycode/data

Abstract

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 lower its crossover points, computed from the main term of the proved bound, by proved changes. For the bound in the number $m$ of clauses, at clause density one, the crossover point drops to about $2^{420}$ clauses from $2^{33858}$; for general 3-SAT, in the number $n$ of variables, our estimate drops to $2^{8.6\cdot10^9}$ variables from $2^{2.2\cdot10^{12}}$. With integer tables the recursion counts, for every $j$, the assignments satisfying exactly $j$ clauses in time $2^{O(m/\sqrt{\log m})}$. We observe that this refutes the Sparse Max-3-SAT Hypothesis of Alman and Vassilevska Williams, which also follows from either refutation by the reduction of Impagliazzo, Paturi and Zane, and we lower the crossover point of this computation to about $2^{1016}$ clauses from $2^{68364}$. The distance is structural: we define a rewrite-and-merge class that contains the recursion and all our constructions, and prove that in the main-term model no grid algorithm in it can gain for general 3-SAT below about $2^{6000}$ variables. For two balanced homogeneous merges we prove with quantum functionals an exponent of at least $(\log_2K)^{-3}$ per edge bit, which excludes running times $2^{n^{1-c}}$. Independently of SAT, we formalise the algorithm as a model of computation, Signed Network Sums, which contains rank-one methods and contraction trees. On the complete graph with four nodes, one-level constructions contract the network in $N^{23/6}$ if $ω=2$ and in about $N^{3.93}$ on the current (preprint) matrix-multiplication curve, below the bound $N^4$ of every rank-one method or contraction tree.

Comment
56 pages. Scripts: https://github.com/Majdoddin/anthropic-3sat-crossover

Closest papers

Nearest neighbours by meaning across the whole index.

Solving Restricted Versions of #SAT Faster than $2^m$: Algorithms and Lower Bounds

cs.DS ·2026-10-11 ·Sanjay Jain, Junqiang Peng, Frank Stephan, Mingyu Xiao
similarity 0.72
Abstract

Under the Strong Exponential Time Hypothesis (SETH), for any constant $\varepsilon > 0$, the #SAT problem (counting the number of satisfying assignments of a CNF formula) cannot be solved in $\mathcal{O}^*((2-\varepsilon)^n)$ or $\mathcal{O}^*((2-\varepsilon)^m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. On the other hand, simple exhaustive search and the standard inclusion-exclusion give $\mathcal{O}^*(2^n)$-time and $\mathcal{O}^*(2^m)$-time algorithms, respectively. A natural line of research is to beat these SETH-based barriers for restricted versions, such as #$k$-SAT (where each clause contains at most $k$ literals) or #$d$-occ-SAT (where each variable appears in at most $d$ clauses). It is known that the $2^n$-barrier can be broken when $k$ or $d$ is any constant; yet, whether the $2^m$-barrier can also be broken in these cases remains unknown. We present two simple algorithms that overcome the $2^m$-barrier. First, for #$k$-SAT, we give an $\mathcal{O}^*(2^{m(1-1/O(k))})$-time algorithm, thereby breaking the $2^m$-barrier for any constant $k$. Second, for #$2$-occ-SAT (which also includes the problem of counting the number of edge covers in a graph as a special case), we provide an algorithm with runtime $\mathcal{O}^*(2^{mω/3})$, where $ω< 2.3714$ is the matrix multiplication exponent. Furthermore, we demonstrate that both algorithms generalize to the weighted counting setting while preserving the same runtime bounds. On the hardness side, we present a reduction from #Max-$d$-SAT to #$d$-occ-SAT, showing that for any $d\ge 3$, #$d$-occ-SAT admits no $\mathcal{O}^*((2-\varepsilon)^m)$-time algorithm for any constant $\varepsilon>0$, even on positive formulas, under the hypothesis that #Max-3-SAT on $n$ variables admits no $\mathcal{O}^*((2-\varepsilon)^n)$-time algorithm for any such $\varepsilon$.

0.29

Faster #PPM from faster #3SAT

cs.DS cs.CC ·2026-10-29 ·László Kozma
similarity 0.67
Abstract

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 PPM and #PPM, is $O(1.415^n)$ (Gawrychowski and Rzepecki). It is also known that PPM is ETH-hard: an algorithm with running time $2^{o(n/\log{n})}$ would imply a subexponential algorithm for 3SAT (Jelínek, Opler, and Pekárek). We give a reduction in the opposite direction, showing that an algorithm for counting satisfying assignments of a 3-CNF formula (#3SAT) in time $2^{O({n}/{f(n)})}$, where $n$ is the number of variables, yields an algorithm for #PPM with running time $2^{O({n \sqrt{\log{f(n)}/{f(n)}}})}$. In particular, the recently claimed refutation of ETH by OpenAI implies a #3SAT algorithm with an improvement factor $f(n) \in Ω(\sqrt{\log{n}}/\log\log{n})$ in the exponent; this yields, through our reduction, a subexponential algorithm for #PPM.

0.56

An upper bound of 4.268 for the random 3-SAT satisfiability threshold

cs.DM math.PR ·2026-10-06 ·Fedor Vorobyev
theory similarity 0.65
Abstract · 16 pages, 1 figure. Includes a complete Lean 4 formalization and a reproducible rational certificate

We prove that a random 3-SAT formula with $n$ variables and $\lfloor 4.268n\rfloor$ clauses is unsatisfiable with high probability. The satisfiability threshold has attracted considerable attention: successive upper bounds reached 4.4898 in the work of Díaz, Kirousis, Mitsche, and Pérez-Giménez, while the cavity method predicts a value near 4.267. Our bound brings the rigorous upper estimate close to this prediction. The proof builds on earlier interpolation methods, including the energetic approach of Achlioptas and Menchaca-Méndez. We study the smallest number of clauses that any assignment must violate, comparing the random formula with a simpler system of constraints on individual variables. This comparison reduces the bound to a finite calculation, which we verify using exact rational arithmetic. The proof is formalized in Lean 4.

0.26

Tight Variable-Occurrence Bounds and Exponential Separations for Moser--Tardos and WalkSAT on 3-CNF

cs.DS ·2026-11-06 ·Minbo Gao, Kun He, Tao Jiang
similarity 0.65
Abstract

We establish a sharp variable-occurrence threshold for polynomial expected-time convergence for the Moser--Tardos algorithm and the pure random-walk WalkSAT on 3-CNF formulas. For every formula with $m$ clauses and at most two occurrences per variable, both algorithms terminate in $O(m)$ expected updates. This occurrence bound is sharp: we construct an infinite family with at most three occurrences per variable on which both algorithms require $2^{Θ(\sqrt{m})}$ expected updates. Surprisingly, this dynamical transition occurs strictly below the classical NP-completeness threshold at variable-occurrence degree four. We further establish exponential separations between the two algorithms on satisfiable 3-CNF formulas. On one family, WalkSAT terminates in $O(m^4)$ expected flips, whereas MT requires $2^{Ω(m)}$ expected resampling steps. On another, MT terminates in $O(m)$ expected resampling steps, whereas WalkSAT requires $2^{Ω(m)}$ expected flips. These constructions exploit the different ways in which single-variable flips and simultaneous resampling propagate local violations. Our results show that the algorithms' expected running times are incomparable even up to polynomial overhead on the same inputs.

0.33

Fine-Grained Complexity Across the Computational Phase Transition

cs.CC cs.DSmath.PR ·2026-11-02 ·Zhe Ju, Jingcheng Liu, Yitong Yin
theory similarity 0.64
Abstract

How does a computational problem transition from easy to hard? In the hard-core model, approximate counting and sampling are polynomial-time tractable up to tree uniqueness, but worst-case intractable at any constant relative distance above it unless $\mathsf{NP}=\mathsf{RP}$. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On $n$-vertex graphs of maximum degree $d\ge3$, at fugacity $λ=(1+δ)λ_{\mathrm c}(d)$ with sufficiently small $δ\ge0$ that may vanish with $n$, its worst-case mixing time has the form $\exp\{Θ(nδ^2/d)\}n^{1+Θ(1)}$. The upper bound is degree-uniform, and the matching lower bound holds for every fixed $d$. Annealing gives approximate counting with the same running-time upper bound at fixed accuracy. For general sampling and counting algorithms, we establish a robust fine-grained reduction from SAT without assuming a lower bound on SAT's running time. For any fixed $d\ge3$ and $0<γ<1$, a sampling or approximate-counting algorithm running in $\exp\{O((nδ^2/d)^{1-γ})\}\operatorname{poly}(n)$ time along any one suitable inverse-polynomial distance sequence $δ=δ(n)$, yields a randomized SAT algorithm running in $\exp\{\widetilde O(s^{1-γ})\}$ time on inputs of binary length $s$. This power-saving transfer identifies $nδ^2/d$ as the analogue of SAT input length for hard-core sampling and counting at relative distance $δ$ above criticality: beating the Glauber exponent by a fixed power through any sampling or counting method would yield a corresponding power improvement for SAT. At criticality, we establish $O(\sqrt{n/d})$ spectral independence, optimal in $n$ at fixed degree, and degree-uniform Glauber mixing in $\widetilde O(n(n/d)^{1+1/(d-2)})$ time, improving the previous $\widetilde O(n^{4+4/(d-2)})$ bound.

0.51

ETH is Dead, Long Live SH

cs.CC ·2026-11-02 ·MIT Hardness Group, Josh Brunner, Erik D. Demaine, Fabian Frei, Timothy Gomez +3 more
theory similarity 0.63
Abstract · 13 pages, 1 table

Impagliazzo and Paturi's 1999 Exponential Time Hypothesis (ETH) is false, but Stearns and Hunt's 1990 Satisfiability Hypothesis (SH) remains plausible. We prove that SH is equivalent to the recently proposed Weak ETH which rules out $O(2^{n^{1-\varepsilon}})L^{O(1)}$-time 3SAT algorithms for every constant $\varepsilon>0$, where $L$ is the input length. We show that SH (or Weak ETH) preserves the typical process for lower bounds: a polynomial-time reduction from a 3SAT formula of size $s=Θ(n+m)$ to an instance of size $N\le s^{b+o(1)}$, for fixed blowup exponent $b>0$, rules out $O(2^{N^{1/b-\varepsilon}})$-time algorithms for every constant $\varepsilon>0$. By comparison, for an $N=O(s^b)$ blowup, ETH would have ruled out $2^{o(N^{1/b})}$-time algorithms. The framework also yields parameterized lower bounds ruling out running times of the form $O(2^{k^{1/b-\varepsilon}})L^{O(1)}$. We also prove equivalence of the analogous counting hypotheses, #SH and Weak #ETH, and that they rule out $O(2^{(n+m)^{1-\varepsilon}})$-time algorithms for #2SAT for every constant $\varepsilon>0$.

0.29

An ETH-based quasipolynomial lower bound for Dualization

cs.DS cs.DM ·2026-10-08 ·Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
theory similarity 0.60
Abstract

Dualizing monotone Boolean functions (or equivalently, enumerating minimal transversals in hypergraphs) is a long-standing problem whose output-polynomial-time solvability remains open. While various special cases have been extensively studied, the state-of-the-art algorithm for the general case, due to Fredman and Khachiyan, runs in quasipolynomial time. This paper presents a subexponential-time reduction from \textsc{3SAT} to the complement of \textsc{Dual}: Given a 3CNF formula with $n$ variables, the reduction constructs hypergraphs $H$ and $L$ of total size $2^{O(n^{2/3}(\log n)^{1/3})}$ such that $L \subseteq Tr(H)$ and the formula is satisfiable if and only if $L\neq Tr(H)$, where $Tr(H)$ is the set of minimal transversals of $H$. As a consequence of this reduction, assuming the Exponential Time Hypothesis (ETH), neither \textsc{Dual} nor \textsc{Dualization} admits an algorithm running in $N^{o(\sqrt{\log N/\log\log N})}$ time, where $N$ is the input size for \textsc{Dual} and the combined input and output size for \textsc{Dualization}. In particular, \textsc{Dualization} cannot be solved in output-polynomial time under ETH.

0.57

Subexponential-Time Exact-One Hitting Set

cs.DS ·2026-10-31 ·Shiteng Chen, Tao Jiang, Yijie Zhu
theory similarity 0.60
Abstract · 33 pages, full version including proofs and appendices

Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.

0.27