Contact us on (02) 8445 2300
For all customer service and order enquiries

Woodslane Online Catalogues

9780898714791 Academic Inspection Copy

Complexity Classifications of Boolean Constraint Satisfaction Problems

Description
Table of
Contents
Google
Preview
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 volume 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. In doing so, they bring out common themes underlying many concepts and results in both algorithms and complexity theory. The results and techniques presented here show that Boolean CSP provides an excellent framework for discovering and formally validating "global" inferences about the nature of computation.
Preface Chapter 1: Introduction Chapter 2: Complexity Classes Chapter 3: Boolean Constraint Satisfaction Problems Chapter 4: Characterizations of Constraint Functions Chapter 5: Implementation of Functions and Reductions Chapter 6: Classification Theorems for Decision, Counting and Quantified Problems Chapter 7: Classification Theorems for Optimization Problems Chapter 8: Input-Restricted Constrained Satisfaction Problems Chapter 9: The Complexity of the Meta-Problems Chapter 10: Concluding Remarks Bibliography Index
Google Preview content