Hard Problems for CSP Algorithms

Weprove exponential lower bounds on the running time of manyalgorithms 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 impfications for the practice of algorithm design.

Authors

• David G. Mitchell Eugenia Ternovska

Keywords

No keywords are indexed for this paper.