CS Paper Radar

Subsumption-Free Private-Pivot Learning in Resolvable Network-Based SAT Solving

Gábor Kusper

cs.LO ·submitted 2026-09-28 10:57 UTC · v1
publishedtheory

Abstract

A resolvable network is a directed-graph representation of SAT: every SAT instance can be translated into an RN, and every RN has an associated CNF formula. Each reach represents one clause. In a mixed reach, the head and tail are disjoint sets of variables containing the variables occurring negatively and positively in the clause, respectively; the distinguished symbols Source and Sink represent a missing negative- or positive-literal side. RN-Solver is a proof-of-concept SAT solver based on this representation. Its all-positive clauses are represented by white reaches, and its token distributions are the inclusion-minimal hitting sets of the current white tails, generated by monotone CNF-DNF dualization. RN-Solver learns new white reaches by private-pivot resolution, a structured resolution sequence that uses old white reaches as pivot witnesses. In the original algorithm, every candidate white reach generated by such a chain was followed by a global subsumption test against the current network. Profiling showed that this subsumption test can dominate the runtime on random 3-SAT instances. We show that this check is unnecessary when the mixed reach used for learning is falsified by the current token distribution, meaning that the distribution makes all variables in the head true and all variables in the tail false. The key invariant is simple: the resulting white tail is disjoint from the triggering token distribution, while the same distribution intersects every old white tail. Hence no old white reach can subsume the generated reach. This structural observation allows us to construct a simpler, snapshot-based, subsumption-free variant of RN-Solver, where each main-loop iteration uses a fixed set of old reaches and installs newly generated white reaches only at the end of the iteration. We prove soundness of the revised algorithm. Empirical evaluation confirms the elimination of the targeted checks: within an 8 second budget, snapshot/full-DNF solves 963 of 1,000 uf20-91 instances, compared with 724 for the original control flow. A separate 100-instance comparison identifies exact incremental DNF as the most effective of the three tested configurations.

Comment
In Proceedings FROM 2026, arXiv:2609.30324
Journal ref
EPTCS 452, 2026, pp. 35-50
DOI
10.4204/EPTCS.452.3

Closest papers

Nearest neighbours by meaning across the whole index.

A Non-CDCL SAT Solver with Early Conflict Detection: The Watched-Literal-Based CSFLOC Solver

cs.LO ·2026-08-25 ·Gábor Kusper
published similarity 0.66
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

CSFLOC is a non-CDCL SAT decision procedure based on counting subsumed full-length ordered clauses. The classical CSFLOC loop traverses the ordered space of full-length clauses by a monotone counter: if the current full-length clause is not subsumed by the input formula, its negation is a satisfying assignment; otherwise, a subsuming clause determines a counter jump. The main bottleneck is the repeated search for such a subsuming clause. This paper presents CSFLOC-WL, and its current implementation CSFLOC-WL3, in which this search is replaced by watched-literal prefix propagation over the negation of the current full-length clause represented by the counter. The central mechanism is early conflict detection: if propagation under a common prefix derives opposite unit consequences for the same variable, then the two reason clauses are resolved immediately and the resolvent is used as a new counter-jump cause. The resulting solver is not a CDCL solver: it has no CDCL decision tree, no restart policy, and no first-UIP backjumping loop. It remains a counter-guided full-length-clause-counting solver, but it imports the watched-literal data structure and reason clauses as engineering tools for discovering jumps. Experiments on selected UNSAT SATLIB instances compare CSFLOC-WL3 with CSFLOC21TU and CaDiCaL 3.0.0. The results are mixed: CSFLOC-WL3 is strong on several random 3-SAT instances near the random-3-SAT satisfiability threshold, whereas CSFLOC21TU remains faster on several structured cases, apparently because it contains a more mature cache mechanism that is not yet present in CSFLOC-WL3.

0.37

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.65
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

Improved Deterministic Algorithms for $k$-SAT: Generalization of Chains and Recurrence Proof

cs.DS ·2026-11-12 ·Binbin Cui, S. Cliff Liu, Yongrui Yu
similarity 0.63
Abstract

We present a deterministic algorithm for 3-SAT running in $1.32736^n$ time. The algorithm is built on a branching-and-chain framework augmented with a polynomial-time expansion procedure that joins short chains through additional clauses to form bounded-size blocks, which impose stronger constraints on the assignment space. After branching, the algorithm chooses between derandomized local search guided by the block structure and enumeration of block assignments together with selected port variables, reducing the remaining formula to 2-SAT. A weighted analysis of branching, partial-assignment, and local-search costs, together with inductive bounds for chains and block interactions, establishes the running-time guarantee. The framework is self-contained and also offers guidance for practical SAT solver design by identifying useful clause-overlap structures and suggesting when to switch between local-search and reduction-based strategies.

0.27

On Structure-Aware SAT Solving

cs.LO ·2026-11-13 ·Eugene Goldberg
hot direction similarity 0.63
Abstract

Although modern SAT solvers have made remarkable progress, they still exploit formula structure only to a limited extent. We present two techniques that make SAT solving more structure-aware and provide experimental results showing their promise. The first technique ``$\mathit{melts}$'' the formula by reducing interaction between its parts. This is achieved by adding new variables, using existential quantifiers, and applying a procedure called partial quantifier elimination. The second technique exploits the notion of a $\mathit{local}$ $\mathit{proof}$. The latter establishes that a formula is unsatisfiable by proving that certain literals of its clauses are redundant. We show that using local proofs makes SAT solving more formula-specific.

0.44

An Improved Algorithm for Quantified Boolean Formulas

cs.DS cs.AI ·2026-11-07 ·Zhiyang Chen, Hailong Yao
similarity 0.63
Abstract

Quantified Boolean formula (QBF), the quantified version of Boolean satisfiability (SAT), is a fundamental problem in constraint solving. Due to the $\mathsf{PSPACE}$-complete nature of QBF, designing theoretically efficient QBF algorithms is much harder and receives less attention in academia. In this work, we present a new algorithm based on memoized search, which solves QBF with $n$ variables and $m$ clauses in $1.685^m\cdot\text{poly}(n)$ time and space. This is the first improvement over the $1.709^m\cdot\text{poly}(n)$ bound by Williams in over 20 years. Our technique is based on the minimum vertex cover of the conflict graphs, which was proposed to study the parameterized complexity of SAT. We extend this idea to QBF and further show that QBF is slicewise polynomial-time solvable using this parameter.

0.22

Reset Early, Reset Often, Eliminate Models

cs.LO cs.AI ·2026-10-13 ·Martin S. Fixman, Fredrik Rømming, Sean B. Holden
publishedbenchmarkcode/data similarity 0.62
Abstract · 13 pages, 6 figures, 5 tables. Presented at Vampire 2026. Code: https://github.com/mfixman/resetsatcop

Connection-tableau provers typically construct closed tableaux by backtracking search. This gives lightweight proof procedures, but their low-memory search state leaves little derived information to reuse after a failed attempt. SATCoP addresses this by retaining grounded tableau clauses in an incremental SAT solver, allowing the prover to refute the problem once the accumulated ground clauses become propositionally unsatisfiable. We introduce SATResetCoP, which relies more directly on this persistent SAT state by not backtracking on unproductive tableaux and instead starting new ones to generate further ground clauses for the SAT solver. On TPTP, SATResetCoP improves over our leanCoP-style baseline by 54% and our SATCoP-style baseline by 18%. On the bushy MPTP2078 benchmark, it solves 616 problems, a 49% improvement over our leanCoP-style baseline and a 12% improvement over our SATCoP-style baseline. These results suggest that changing tableau guidance to accumulate useful ground clauses faster improves the performance of the prover.

0.46

Cores Characterize the One-Pass Streaming Complexity of CSPs

cs.CC cs.DMcs.DS ·2026-10-05 ·Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy
similarity 0.62
Abstract

We study the one-pass streaming complexity of CSPs over a fixed finite relation $R$ under three natural objectives: $\textsf{SAT}(R)$, deciding whether all constraints can be satisfied; $\textsf{Min}$-$\textsf{CSP}(R)$, approximately minimizing the number of unsatisfied constraints; and $\textsf{Exact-CSP}(R)$, exactly computing the maximum number of satisfied constraints. Sharma and Velusamy (ESA 2026) characterized the streaming complexity of satisfiability for CSPs with literals using the non-redundancy parameter $\textsf{NRD}_n(R)$, which roughly measures the largest instance in which every constraint is independently necessary. For the most general setting without literals, they obtained the corresponding characterization for Boolean relations and showed obstacles to extending their techniques to larger domains. Kol, Paramonov, Saxena, and Yu (ITCS 2023) similarly characterized the streaming complexity of $\textsf{Exact-CSP}(R)$ for Boolean CSPs with literals in terms of the degree deg$(R)$ of the relation when written as a polynomial, while without literals, the corresponding result was known only for $\textsf{Max-Cut}$. For all three of the objectives we study, we give tight characterizations for unweighted CSP instances over arbitrary finite domains. The streaming algorithms we provide are deterministic, while the corresponding bounds are tight up to polylogarithmic factors, even against randomized algorithms. The central idea in all three results is a reduction of $R$ to its core, a canonical subrelation of $R$ which admits gadgets that allow for the hard-pinning (or fixing) of variables.

0.15

Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity

cs.DS cs.CC ·2026-10-13 ·Jan Dreier, Robert Ganian, Marlene Gründel, Roohani Sharma, Simon Wietheger
similarity 0.61
Abstract

The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide range of search and reasoning tasks. While $\mathrm{NP}$-complete in general, SAT is well known to be linear-time solvable on instances with bounded treewidth. This motivates the search for "hidden" tree-like structures in formulas---for instance by detecting so-called weak $t$-treewidth backdoors. Such backdoors are sets of $k$ variables that can be assigned in such a way that the remaining instance has treewidth at most $t$ and is satisfiable whenever the original instance is. Ever since Gaspers and Szeider [ICALP 2012] showed that finding a weak $t$-treewidth backdoor for a SAT formula is $\mathrm{W}[2]$-hard with respect to $k$, tractability results have been restricted to structurally sparse formulas---most notably, a linear-time algorithm for $d$-SAT (bounded clause-length SAT) by Fomin, Lokshtanov, Misra, Ramanujan, and Saurabh [SODA 2015] and a non-uniform polynomial-time algorithm when the incidence graph of the input formula belongs to a nowhere-dense graph class (or more generally is $K_{d,d}$-free) by Lokshtanov, Panolan, and Ramanujan [ICALP 2022]. In this paper, we push the tractability boundaries of finding weak $t$-treewidth backdoors beyond sparsity and into the regime of "well-behaved" dense formulas. Aiming towards relaxing structural input restrictions from nowhere-dense to edge-stable graph classes, as featured in the theory of beyond sparsity for FO model checking, or to bounded VC-dimension set systems, we identify signed semi-ladder-freeness as the correct dense structural restriction that establishes the boundary between tractability and intractability along this line.

0.48