The backdoor key A path to understanding problem hardness.pdfVIP

The Backdoor Key: A Path to Understanding Problem Hardness Yongshao Ruan, Henry Kautz Department of Computer Science University of Washington Seattle, WA 98195 ruan@ kautz@ Eric Horvitz Microsoft Research Redmond, WA 98052 horvitz@ Abstract We introduce our work on the backdoor key, a concept that shows promise for characterizing problem hardness in back- tracking search algorithms. The general notion of backdoors was recently introduced to explain the source of heavy-tailed behaviors in backtracking algorithms (Williams, Gomes, Selman 2003a; 2003b). We describe empirical studies that show that the key faction,i.e., the ratio of the key size to the corresponding backdoor size, is a good predictor of problem hardness of ensembles and individual instances within an en- semble for structure domains with large key fraction. Introduction Propositional reasoning (SAT) is the best-known NP- complete problem in computer science. Even though a class of SAT problems may be intractable in the worst case, most of its instances may still be polynomial-time solvable in practice and their hardness may vary significantly. It has proven extremely difficult in practice to define realis- tic problem ensembles where instances do not vary widely in hardness (Kautz et al. 2001). Different instances have widely varying hardness even in the well-known random 3- SAT problem ensembles with fixed clause-to-variable ratios (Kirkpatrick Selman 1994). In such cases, it is crucial to understand the hidden structures that can be used to identify problem hardness and as points of attack for search heuris- tics. There has been considerable research interest in identify- ing such structures for many years. One example of such hidden structure is the backdoor set (Williams, Gomes, Selman 2003a). Given a SAT formula, a set of variables forms a backdoor for a problem instance if there is a truth as- signment to these variables such that the simplified formula can be solved in polynomial time via use