Hard Problems for CSP Algorithms

Abstract

We prove exponential lower bounds on the running time of many algorithms for Constraint Satisfaction, by giving a simple family of instances on which they always take exponential time. Although similar lower bounds for most of these algorithms have been shown before, we provide a uniform treatment which illustrates a powerful general approach and has stronger implications for the practice of algorithm design. Introduction Finite-domain constraint satisfaction (CSP) is a popular problem solving technique in AI. A CSP instance is a set of variables, and a set of constraints on values assigned to them. Solving an instance requires finding an assignment which satisfies the constraints, or determining that no such assignment exists. In the usual formalizations this task is NP-complete, so a polynomial time algorithm exists if and only if P=NP. Since many practical problems amount to solving CSPs, we want to find the best algorithms we can, regardless of the truth of this proposition. The l...