O'Reilly logo

Handbook of Constraint Programming by Toby Walsh, Peter van Beek, Francesca Rossi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

David Cohen, Peter Jeavons

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required