Introduction
Boolean Satisfiability (SAT) is a cornerstone of computer science, serving as the prototypical NP-complete problem. While modern solvers like Kissat and CaDiCaL exhibit remarkable efficiency on many practical instances, "hard" benchmarks in hardware verification and cryptography remain computationally daunting. A classical approach to tackling these instances involves identifying a Strong Backdoor Set (SBS)—a subset of variables whose assignment simplifies the problem into polynomial-time solvable sub-problems. However, the search for a minimal SBS is itself a hard problem, often exceeding the time required to solve the original instance.
From Backdoor Sets to $\rho$-Backdoor Trees
Recent advancements introduced $\rho$-backdoors, a probabilistic relaxation where only a fraction $\rho$ of truth assignments must lead to easy sub-problems. While effective, searching for these sets using metaheuristics remained slow. This paper proposes a transition from flat sets to $\rho$-backdoor trees.
In this representation, each internal node corresponds to a variable, and each leaf indicates whether the resulting sub-problem is solved by a polynomial-time sub-solver. This structure allows for "early exits": if a partial assignment solves the formula, the tree terminates early, avoiding redundant branching required by flat sets. A key theoretical insight (Theorem 2) reveals that while the probability $\rho$ is invariant to the branching order of variables within a fixed set, the search efficiency and tree size are highly sensitive to this order.
Methodology: Efficient Search and Optimization
To make the search for these trees practical, the authors employ several optimizations:
- Heuristic Search Space: Instead of considering all variables, they restrict the search to the top 200 variables identified by a Unit Propagation (UP) greedy heuristic.
- Evolutionary Optimization: A (1+1) Fast Evolutionary Algorithm minimizes a fitness function that balances tree size against the probability $\rho$.
- Monte Carlo Estimation: To handle large trees where exact calculation of $\rho$ is intractable, a Monte Carlo approach provides rapid statistical estimates.
Experimental Results
The approach was evaluated on hard benchmarks including logic verification ($PvS, BvP, BvS$) and combinatorial problems ($PHP, par9, pmg12, sgen$). The most significant achievement is the reduction in pre-processing time: finding a $\rho$-backdoor tree now takes approximately 3 seconds on a single thread, compared to the 0.5 to 6 hours required by previous multi-threaded set-based methods.
As shown in the results table, the decomposition rate ($r_{B,M}$)—the ratio of solving time with the backdoor versus without—is frequently well below 1.0. For instances like $pmg12$ and $sgen$, the backdoor approach is up to 10 times faster than state-of-the-art solvers like Kissat ($r_{B,ks}$) or CaDiCaL ($r_{B,cd}$).
Conclusion and Future Work
By generalizing backdoors into a tree-based probabilistic framework, this research transforms a heavy pre-processing task into a lightweight optimization step. While currently focused on sequential solving, the tree structure is inherently suited for parallel and cloud-based SAT solving. Future work may explore dynamic variable ordering to further minimize tree sizes and enhance solver performance.
Summary updated