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. 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 provide an
excellent framework for discovering and formally validating
"global" inferences about the nature of computation.
This book presents a novel and compact form of a compendium that
classifies an infinite number of problems by using a rule-based
approach. This enables practitioners to determine whether or not a
given problem is known to be computationally intractable. It also
provides a complete classification of all problems that arise in
restricted versions of central complexity classes such as NP, NPO,
NC, PSPACE, and #P.
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Review This Product
No reviews yet - be the first to create one!