Foundations of Artificial Intelligence, Vol. 2, Suppl. (C), 2006
ISSN: 1574-6526
doi: 10.1016/S1574-6526(06)80012-X
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 [72], 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 ...
Get Handbook of Constraint Programming now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
