Hard Problems for CSP Algorithms

David G. Mitchell

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.