Complexity classifications of Boolean constraint satisfaction problems (Q2723175)

Complexity theory deals with infinitely many complexity classes, infinitely many questions, and innumerable possible resolutions to these questions. This powerful feature has a severely limiting factor in its scope. It limits the ability to present results compactly.NEWLINENEWLINENEWLINEThis monograph attempts to break free of these inherent barriers in the study of complexity theory by restricting its attention to a microcosmos of computational problems, Boolean constraint satisfaction problems. This restricted class of problems continues to exhibit much of the natural diversity of computational problems without exhibiting the corresponding limitations. In particular, the Boolean constraint version of the complexity classes known from general complexity theory can be defined. These classes continue to have a rich collection of complete problems. They continue to have infinitely many different problems. However, it turns out that it is possible to completely classify the complexity of all the problems of these classes -- one of the book's goals is to present results of the form ``If all constraints in a given set \(F\) of templates satisfy a certain property \(P\), then a canonical algorithm can be applied to solve the corresponding constraint satisfaction problem efficiently; the absence of the property \(P\) says that solving the constraint satisfaction problem associated with \(F\) is hard''.NEWLINENEWLINENEWLINEBy focusing on this restricted world, it is possible to present a reasonably accurate bird's eye view of complexity theory.NEWLINENEWLINENEWLINEThe book is written for researchers in optimization and computer science who spend a good deal of their time analyzing new computational problems. Furthermore, the book is as self-contained as possible and could be followed by any student who has taken the first course on the theory of computation.