Ryan Williams: Backdoors to Typical Case Complexity

Videos from the Beyond Worst Case Analysis Workshop Stanford, CA Sept 19-21, 2011 Ryan Williams: Backdoors to Typical Case Complexity In areas such as planning and finite model-checking, current solution techniques can solve combinatorial problems with millions of variables and constraints. The good scaling behavior of these methods appears to defy what one would expect based on worst-case complexity. This talk will survey a framework for understanding the tractability of real-world problem instances, developed in collaboration with Gomes and Selman. The central concept is that of a "backdoor" to an instance: a small variable subset "sufficient" for solving that instance. Informally, a backdoor measures the "distance" of a problem instance from a polynomial-time solvable subset of instances. Empirical results have shown that many real-world problems possess small backdoors (with respect to polynomial-time heuristics built into the solvers), and much theoretical work on parametrized and exact algorithms can be reinterpreted in the language of backdoors.