Metraipolis › archive › dc_f3573391c40d
Lowered crossover points of Anthropic's subexponential 3-SAT algorithm — arXiv:2610.41622
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.41622
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T05:49:25.193Z
- SHA-256 of the archived text
5776845b3c84e6da896637b9f6663e25b0bdb85093434698d428dc1360b39de0- Stable URL of this page
https://metraipolis.com/documento/dc_f3573391c40d
How to cite
Lowered crossover points of Anthropic's subexponential 3-SAT algorithm — arXiv:2610.41622 — arXiv (en), https://arxiv.org/abs/2610.41622 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f3573391c40d (Metraipolis archive dc_f3573391c40d, sha256 5776845b3c84e6da896637b9f6663e25b0bdb85093434698d428dc1360b39de0)
BibTeX
@misc{dcf3573391c40d,
title = {Lowered crossover points of Anthropic's subexponential 3-SAT algorithm — arXiv:2610.41622},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.41622},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f3573391c40d; sha256 5776845b3c84e6da896637b9f6663e25b0bdb85093434698d428dc1360b39de0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41622. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\omega=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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41622 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:34:47.028Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).