Backdoors to typical case complexity

By Ryan Williams, Carla P. Gomes, Bart Selman. International Joint Conference on Artificial Intelligence, 2003

389 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Using Expectation Maximization to Find Likely Assignments for Solving CSP's (2007, background): “At an intuitive level, this roughly corresponds to the notion that problems have a few “backdoor” [19, 13] variables that, when set correctly, render the remaining problem polynomially solvable by a simpler method.”
Predicting Learnt Clauses Quality in Modern SAT Solvers (2009, background): “Those benchmarks share a very particular structure: they often contain very small backdoors sets [Williams et al. , 2003], which, intuitively, encode inputs of formulas.”
Boosting Systematic Search by Weighting Constraints (2004, background): “In fact, one should ideally use a variable ordering that selects first a small (strong) backdoor [27], i.”