Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search

摘要

There has been considerable interest in the identification of structural properties of combinatorial problems that lead to efficient algorithms for solving them. Some forms of structure, such as properties of the underlying constraint graph, are "easily" identifiable. Others, such as backdoor sets, are of interest because they capture key aspects of state-of-the-art constraint solvers as well as of many real-world problem instances. While backdoors were originally introduced to capture propagation based simplification mechanisms of solvers, they have recently been studied also in the context of tractable syntactic classes such as 2CNF and Horn. These syntactic classes, however, do not capture key aspects of solvers such as empty clause (i.e., violated constraint) detection. We show that incorporating inconsequential sounding features such as empty clause detection has a dramatic impact on both the complexity of finding a backdoor of size k (which becomes harder in the worst case) and on the size of the resulting backdoor (which can become arbitrarily smaller). Empirically, we show that commonly employed polynomial-time "dynamic" constraint propagation mechanisms, such as unit propagation, pure literal elimination, and probing, often lead to much smaller backdoor sets in real-world domains than "statically" defined classes such as Horn and RHorn, thereby capturing structure much more succinctly. We also reveal the inherent limits of the simpler concept of deletion backdoors, specifically by looking at renamable Horn sub-formulas. Finally, we extend the notion of backdoors to incorporate learning during search-a key aspect of nearly all state-of-the-art systematic SAT solvers-and show, both theoretically and empirically, that this drastically reduces the size of the resulting backdoor set. Our results suggest that structural notions explored for designing efficient algorithms for combinatorial problems should capture both statically and dynamically identifiable properties of the combinatorial problem being solved.