Relating Complexity-theoretic Parameters with SAT Solver Performance
This work addresses the need for better theoretical understanding of SAT solver performance, though it is incremental as it builds on existing parameters and empirical analysis.
The study tackled the problem of explaining the efficiency of CDCL SAT solvers by evaluating structural parameters like backdoors and treewidth on nearly 7000 formulas, finding that combinations of parameters yield better regression models and proposing a new parameter, LSR backdoors, which can be exponentially smaller than existing ones.
Over the years complexity theorists have proposed many structural parameters to explain the surprising efficiency of conflict-driven clause-learning (CDCL) SAT solvers on a wide variety of large industrial Boolean instances. While some of these parameters have been studied empirically, until now there has not been a unified comparative study of their explanatory power on a comprehensive benchmark. We correct this state of affairs by conducting a large-scale empirical evaluation of CDCL SAT solver performance on nearly 7000 industrial and crafted formulas against several structural parameters such as backdoors, treewidth, backbones, and community structure. Our study led us to several results. First, we show that while such parameters only weakly correlate with CDCL solving time, certain combinations of them yield much better regression models. Second, we show how some parameters can be used as a "lens" to better understand the efficiency of different solving heuristics. Finally, we propose a new complexity-theoretic parameter, which we call learning-sensitive with restarts (LSR) backdoors, that extends the notion of learning-sensitive (LS) backdoors to incorporate restarts and discuss algorithms to compute them. We mathematically prove that for certain class of instances minimal LSR-backdoors are exponentially smaller than minimal-LS backdoors.