Complexity Classifications of Boolean Constraint Satisfaction Problems |
|
| Author:
| Creignou, Nadia
Khanna, Sanjeev
Sudan, Madhu |
| Series title: | SIAM Monographs on Discrete Mathematics and Applications Ser. |
| ISBN: | 978-0-89871-479-1 |
| Publication Date: | Mar 2001 |
| Publisher: | Society for Industrial and Applied Mathematics
|
| Book Format: | Hardback |
| List Price: | USD $58.00USD $85.50 |
Book Description:
|
Many fundamental combinatorial problems, arising in such diverse fields as artificial intelligence, logic, graph theory, and linear algebra, can be formulated as Boolean constraint satisfaction problems (CSP). This book is devoted to the study of the complexity of such problems. The authors' goal is to develop a framework for classifying the complexity of Boolean CSP in a uniform way.
Many fundamental combinatorial problems, arising in such diverse fields as artificial intelligence, logic, graph theory, and linear algebra, can be formulated as Boolean constraint satisfaction problems (CSP). This book is devoted to the study of the complexity of such problems. The authors' goal is to develop a framework for classifying the complexity of Boolean CSP in a uniform way.