Papers for

sat solver developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Strong backdoors to forests found efficiently in general sat problems

Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SAT

Abstract: In a seminal work, Gaspers and Szeider [FOCS 2013] gave a fixed-parameter tractable (FPT) approximate algorithm for finding a strong backdoor of size at most $k$ to incidence treewidth at most $t$, for a given CNF-formula $φ$. In particular, their algorithm runs in $f(k,t) |φ|^3$ time, and finds a strong backdoor to treewidth at most $t$, of $φ$, of size at most $2^k$ whenever there exists one of size at most $k$. Determining whether the detection of strong backdoors to bounded incidence treewidth is FPT parameterized by $k+t$ was left open in their work and this has been repeatedly posed as an open question by Gaspers and Szeider, for example in [The Multivariate Algorithmic Revolution and Beyond 2012] and more recently in [Computer Science Reviews 2025], even for incidence forests and when the input is a $3$-CNF formula. We answer this question affirmatively. We show that strong backdoors to forests can be found in linear-FPT time on arbitrary non-tautological CNF formulas (not just on 3-CNF formulas). Given such a formula $φ$ and a budget $k$, our algorithm finds a strong backdoor to the class of forests, of size at most $k$, or correctly reports that none exists, in $2^{2^{O(k)}} |φ|$ time. Moreover, we show that our result is as tight as it can get. First, we show that finding strong backdoors to treewidth $t$ for any $t \geq 2$ is W[1]-hard, even on non-tautological 3-CNF formulas. Second, the running time of our algorithm is tight: it is linear in the input size and a better than double-exponential dependence on $k$ in the running time would imply a $2^{o(N/\log N)}$-time algorithm for solving 3-SAT on $N$ variables, which would beat even the very recently claimed sub-exponential algorithm for solving 3-SAT by OpenAI and Anthropic.

Mon 9 NovData Structures and AlgorithmsComputational Complexity
The gist
Finding small sets of variables that simplify complicated logic problems is very useful but often hard to do quickly. The authors answered a long-standing question by showing it is possible to find these sets, called strong backdoors to forests, in linear time with respect to the input size, even for very general formulas. They also proved that this speed is about as good as anyone can hope for unless a major breakthrough happens in solving 3-SAT problems. The work advances our understanding of which logical structures can be detected efficiently.
Open → 2611.12321v1

Finding treewidth backdoors enables faster SAT solving beyond sparse cases

Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity

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.

Tue 13 OctData Structures and AlgorithmsComputational Complexity
The gist
The Boolean Satisfiability (SAT) problem involves checking if certain logical formulas can be satisfied, which is usually hard for computers. It's easier to solve when the formulas have a tree-like structure. The authors study special sets of variables, called weak treewidth backdoors, which reduce complexity if assigned correctly. They discover new conditions that allow finding these helpful variable sets efficiently even in dense formulas, not just sparse ones. This expands the range of SAT problems that can be solved faster.
Open → 2610.18540v1

Multiplication associativity is provably hard for SAT solvers

Associativity of Multiplication Is Hard for Resolution

Abstract: SAT solvers are empirically known to perform poorly when reasoning about multiplication. Yet for over a decade we have lacked a theoretical explanation for this phenomenon. CDCL SAT solvers implicitly search for resolution proofs, and no lower bound on proof size has ruled out the existence of short proofs that solvers simply fail to find. We give the first lower bound of this kind by showing that general resolution proofs of the associativity of $n$-bit multiplication require size $2^{Ω((n/\log n)^{1/4})}$. This lower bound holds for a broad class of multiplier encodings based on partial product summation, including the standard array and Wallace-tree multipliers used to bit-blast multiplication in SMT solvers. This result resolves an open problem of Beame and Liew. The proof constructs a reduction from a perfect-matching principle on bounded-degree bipartite expander graphs to multiplier associativity. Itsykson, Slabodkin, and Sokolov proved that this principle is hard for resolution. The lower bound for multiplier associativity follows. The same reduction, when combined with Håstad's recent lower bound for the perfect-matching principle of the odd grid, yields an exponential lower bound for multiplier associativity in the stronger bounded-depth Frege proof systems.

Tue 6 OctComputational ComplexityLogic in Computer Science
The gist
Multiplying numbers is a basic math operation, but computers that solve logical puzzles called SAT solvers struggle to prove that multiplication works the same way no matter how you group numbers (associativity). The authors show that the logical steps needed to prove this are very large and complex, explaining why these solvers perform poorly. They connect this difficulty to another well-known hard logic problem and prove strong limits on how simple any proof can be.
Open → 2610.08988v1