Foundations of Artificial Intelligence, Vol. 2, Suppl. (C), 2006
Chapter 8 The Complexity of Constraint Languages
One of the most fundamental challenges in constraint programming is to understand the computational complexity of problems involving constraints. It has been shown that the class of all constraint satisfaction problem instances is NP-hard , so it is unlikely that efficient general-purpose algorithms exist for solving all forms of constraint problem. However, in many practical applications the instances that arise have special forms that enable them to be solved more efficiently [11, 25, 70, 83].
One way in which this occurs is that there is some ...