Probabilistic Generalization of Backdoor Trees with Application to SAT

Alexander A. Semenov, Daniil Chivilikhin, Stepan Kochemazov, Ibragim DzhiblaviAAAI 2023 · DOI

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.

A binary tree representation of a backdoor, where internal nodes are variables and paths represent truth assignments.

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:

  1. 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.
  2. Evolutionary Optimization: A (1+1) Fast Evolutionary Algorithm minimizes a fitness function that balances tree size against the probability $\rho$.
  3. 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.

Performance metrics for various SAT instances, showing high $\rho$ values and significant decomposition rates ($r_{B,ks}, r_{B,cd}$).

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

BibTeX
@inproceedings{semenov2023probabilistic,
  author = {Alexander A. Semenov and Daniil Chivilikhin and Stepan Kochemazov and Ibragim Dzhiblavi},
  title = {{Probabilistic Generalization of Backdoor Trees with Application to SAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25525},
}
Figure