Creignou N., Khanna S., Sudan M. Complexity Classifications of Boolean Constraint Satisfaction Problems

Society for Industrial and Applied Mathematics, 2001, -119 pp.This book presents a nearly complete classification of various restricted classes of computational problems called Boolean constraint satisfaction problems. Roughly, these are problems whose instances describe a collection of simple constraints on Boolean variables. A typical goal would be to find a setting to the Boolean variables that satisfies all the constraints. Variants of the problem may make the goal determining if such a setting exists, or counting the number of such settings or determining the "optimal" setting among those that satisfy all constraints, etc. This book studies all such problems and presents complexity results classifying them.
Constraint satisfaction problems are interesting in their own right. They occur commonly in practice, in optimization and in settings arising from artificial intelligence. This book presents a compact collection of rules that classify every constraint satisfaction problem as "easy" or "hard". Such a compact and complete classification of these problems has obvious utility to the practitioners that encounter such problems. The fact that there are infinitely many constraint satisfaction problems hints that the practitioner is likely to encounter a new one every once in a while. The typical researcher at this stage would either end up chasing references in a library or attempt to (re)solve this new computational problem: this book offers an alternative to these paths. It offers a calculus, or a guidebook of rules, that characterizes the complexity of this new problem and its numerous variants, while also presenting the best possible algorithm for solving this problem!
Such a calculus characterizing the complexity of computational problems is obviously of interest to "complexity theory" — the area that studies the computational complexity of solving mathematical problems. Complexity theory studies the complexity of solving any/every computational problem. The focus of this book may be considered a restriction of this goal — it focuses its attention on a restricted subclass of all problems.
The natural question to ask at this stage is: Why focus on a restricted class when one could study complexity theory in its full generality? The reason is that complexity theory is so general that its results become too weak. In its full scope, complexity theory easily possesses the ability to study itself, and therein subjects itself to the problem of diagonalization. This problem soon manifests itself everywhere. It suggests it is not possible to come up with simple rules saying when a problem is "easy" or "hard". (This is merely one of the many disastrous implications of a well-known theorem of Rice.) It blinds us from seeing evident generalizations of known principles, such as when a seemingly general technique (an algorithm or a hardness result) can be applied to a whole class of problems. As a consequence, most results are presented in isolated form — addressing one problem at a time.
This is where Boolean constraint satisfaction problems come to our rescue. They are not too general, so they don't succumb to diagonalization arguments; thus, a complete classification is not necessarily infeasible. And as we will show in this book, such a classification indeed exists and can be derived fairly easily. However, existence of the classification alone does not provide sufficient motivation to read about it. After all, if one restricts the class of problems sufficiently, a classification should not be hard! So to justify the restriction we still need to say why constraint satisfaction problems are of interest to the complexity theorist: this is easy. Take any of the standard texts on complexity and the first problem that is shown to be the canonical (complete) representative for a given class is typically a constraint satisfaction problem. Constraint satisfaction problems thus form the nucleus of many complexity classes, and could be interpreted to be the combinatorial core of complexity. This realization has been implicit to the researchers in complexity theory for several decades now and is brought out explicitly in this book. This book studies the restriction of many different complexity classes to constraint satisfaction problems. It unifies the techniques used to analyze all the different variants and formally justifies the many coincidences that were often observed about computation in the past.
Above, we have described two potential audiences for this book: Researchers in optimization/computer science who spend a good deal of their time analyzing new computational problems, for whom this book could be a handy reference, and researchers in complexity theory and discrete mathematics. There are many reasons for which the audience in the latter category may choose to read this book. The results presented here are a compact description of a large body of results proven in numerous papers. Moreover, the proofs presented here are often simpler than the ones presented in the original papers. But we view these as the secondary reasons to read this book. The primary reason is to learn about the potential importance of Boolean constraint satisfaction problems to their own area of work. These problems are an excellent testbed for abstracting some "global" inferences about the nature of computation, and may provide very useful hints at some hidden truths.
This book is intended for researchers and graduate students pursuing theoretical computer science or discrete mathematics. It was written with an awareness that the audience described above need not always share a common language or definitions. Thus we have attempted to keep the book as self-contained as possible. It is our hope that any reader who has taken the first course on the "Theory of Computation" should be in a position to follow the text fully. Comments from the readers on this or other aspects of the book (via email to creignouOlim.univ-mrs.fr, sanjeevocis.upenn.edu or madhu@mit.edu) will be most welcome.Complexity Classes
Boolean Constraint Satisfaction Problems
Characterizations of Constraint Functions
Implementation of Functions and Reductions
Classification Theorems for Decision, Counting and Quantified Problems
Classification Theorems for Optimization Problems
Input-Restricted Constrained Satisfaction Problems
The Complexity of the Meta-Problems
Concluding Remarks