On Probabilistic Generalization of Backdoors in Boolean Satisfiability

Alexander A. Semenov, Artem Pavlenko, Daniil Chivilikhin, Stepan KochemazovAAAI 2022 · DOI

Introduction

The Boolean Satisfiability Problem (SAT) remains a cornerstone of computer science, serving as the fundamental NP-complete problem with critical applications in hardware verification, cryptography, and automated reasoning. While modern Conflict-Driven Clause Learning (CDCL) solvers are remarkably efficient, they frequently encounter "walls" when faced with specific classes of hard combinatorial instances.

One established technique for scaling SAT solving is the use of Strong Backdoor Sets (SBS). A backdoor is a subset of variables such that assigning values to them reduces the remaining formula to a subproblem solvable in polynomial time. However, finding the smallest SBS is itself a computationally intensive task, often rendering traditional search algorithms impractical for large-scale problems. This research addresses the gap between theoretical backdoor sets and practical solver performance by introducing a probabilistic relaxation of the concept.

The $\rho$-Backdoor Approach

The authors propose $\rho$-backdoors, a generalization that shifts the requirement from absolute certainty to probabilistic efficiency. Instead of demanding that every possible assignment to the backdoor variables results in an easy subproblem, a $\rho$-backdoor only requires a fraction $\rho$ (e.g., 99%) of assignments to be tractable.

To implement this, the researchers utilize several key strategies:

  1. Monte Carlo Estimation: Since exhaustive checking of all assignments is exponentially expensive, the quality of a variable set (the value of $\rho$) is estimated through sampling. This leads to the definition of an $(\epsilon, \delta)$-SBS, a set that is statistically likely to be a high-quality backdoor within defined error margins.
  2. Metaheuristic Search: Finding these sets is framed as an optimization problem. The authors employ Genetic Algorithms (GA) to navigate the discrete search space of variable subsets. The fitness function is designed to minimize the set size while maximizing the estimated $\rho$.
  3. Penalty Functions: To guide the GA, a penalty function is used to heavily discount variable sets where the underlying subsolver (typically Unit Propagation) fails to resolve the sampled subproblems quickly.

Experimental Evaluation

The methodology was tested against several "hard" unsatisfiable Conjunctive Normal Form (CNF) benchmarks, including equivalence checking instances (PvS, BvP, BvS) and crafted combinatorial problems like the Pigeonhole Principle (PHP) and the pmg12 instance from SAT competitions. Underlying solvers used for comparison included Glucose (3.0 and 4.1) and CaDiCaL.

Figure 1: Solving time decreases significantly as the number of $\rho$-backdoors used in the decomposition strategy increases.

One of the most powerful insights from the study is the Multi-Backdoor Strategy. Because a single $\rho$-backdoor might leave a small percentage of "hard" assignments, combining multiple different backdoors allows the solver to effectively cover the entire difficulty space of the original problem. As shown in Figure 1, increasing the number of backdoors leads to a consistent reduction in total solving time across different solver engines.

Key Results

The probabilistic approach yielded significant performance gains over standalone state-of-the-art solvers:

  • Massive Speedups: On the PvS4,7 instance, the multi-backdoor approach achieved a decomposition rate ($r_{\Delta,A}$) as low as 0.06. This indicates the problem was solved approximately 16 times faster than by the standalone solver.
  • Solving "Unsolvable" Instances: The pmg12 benchmark, which famously resisted Glucose 3.0 and 4.1 even after 72 hours of computation, was successfully solved in a fraction of that time using a set of four $\rho$-backdoors.
  • Search Efficiency: The pre-processing cost to find these backdoors (typically 30 minutes to 6 hours on a cluster) is well-justified for instances that would otherwise require days of processing or remain unsolved.
Figure 4: Performance metrics for multi-backdoor sets, showing the number of backdoors (s) and the resulting decomposition rate ($r_{\Delta,A}$) for various hard instances.

Conclusion

By relaxing the requirement for "perfect" backdoors, this research demonstrates that "mostly-good" backdoors found via metaheuristic search can provide a practical path to solving some of the most difficult SAT instances. Future work may involve refining the fitness function parameters and extending the methodology to satisfiable formulas, where the definition of "hardness" is more dynamic.

Summary updated

BibTeX
@inproceedings{semenov2022probabilistic,
  author = {Alexander A. Semenov and Artem Pavlenko and Daniil Chivilikhin and Stepan Kochemazov},
  title = {{On Probabilistic Generalization of Backdoors in Boolean Satisfiability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21277},
}
Figure