Backdoors to typical case complexity

摘要: There has been significant recent progress in reasoning and constraint processing methods. In areas such as planning finite model-checking, current solution techniques can handle combinatorial problems with up to a million variables five constraints. The good scaling behavior of these methods appears defy what one would expect based on worst-case complexity analysis. order bridge this gap between theory practice, we propose new framework for studying the practical problem instances. particular, our approach incorporates general structural properties observed instances into formal We introduce notion "backdoors", which are small sets that capture overall combinatorics instance. provide empirical results showing existence backdoors real-world problems. then present series explain