This book presents an introduction to the theory of constraint satisfaction problems (CSPs) that was developed over the last 25 years in order to understand how the computational complexity of such problems depends on their mathematical structure. The essential components of this theory are universal algebra and model theory, occasionally helped by other branches of mathematics, e.g., topology and Ramsey theory. Much of this theory is of significant independent mathematical interest.
The subject of the book is an interplay between three large separate research areas: complexity of CSPs, universal algebra, and model theory. Apart from those already working on the interface of these areas, it is not common to have a detailed knowledge of all three. The book is a very good attempt to ease the way into its subject for those wishing to understand this interplay, which I believe would be a very enriching experience, both for seasoned researchers and for graduate students. The book presents the foundations of mathematical theory of CSPs, but this is a very active research area, with many open problems and many new results appearing every year.
The book is very thorough and well-structured. Every chapter starts with an intuitive explanation of the role of the material presented in it in the general theory. Full detailed proofs are given for most statements, as is appropriate for an introductory textbook. Many examples are given throughout to illustrate both the concepts involved and the applications of the theory. The book concludes with an overview of future research directions and a list of open problems.
The book assumes familiarity with very basic knowledge of the computational complexity theory: specifically, the classes
$\text {P}$
and
$\text {NP}$
, and the notions of polynomial-time reduction and
$\text {NP}$
-completeness. Not having this knowledge is not a serious obstacle, as one can quickly obtain it from many excellent textbooks and online resources.
The book is concerned with the following class of CSPs that receives much attention in the literature. Fix a relational structure
$\mathbf {A}$
(often referred to as a template or as a constraint language). The CSP of
$\mathbf {A}$
, denoted by
$\mathrm {CSP}(\mathbf {A})$
, is the problem of deciding whether a given finite structure
$\mathbf {I}$
admits a homomorphism to
$\mathbf {A}$
. For example, the classical graph k-coloring problem (of deciding whether the vertices of a given graph can be colored with k colors so that no adjacent vertices get the same color) is
$\mathrm {CSP}(\mathbf {K}_k)$
where
$\mathbf {K}_k$
is the complete graph on k vertices. Many problems from different areas of mathematics and computer science can be cast as
$\mathrm {CSP}(\mathbf {A})$
for a suitable
$\mathbf {A}$
- the book gives plenty of examples of such problems.
It is well known that if
$\text {P}\ne \text {NP,}$
then
$\text {NP}$
contains many
$\text {NP}$
-intermediate problems - that are neither in
$\text {P}$
nor
$\text {NP}$
-complete. Feder and Vardi initiated in 1990s the search for a large natural subclass of
$\text {NP}$
that exhibits a dichotomy, i.e., avoids intermediate problems. They famously conjectured that the class of problems
$\mathrm {CSP}(\mathbf {A})$
with finite
$\mathbf {A}$
has such a dichotomy. This conjecture (that was recently confirmed independently by Bulatov and Zhuk) was considered to be among the most important open problems in theoretical computer science.
The key component in the theory of CSPs is the (universal-)algebraic approach, and the book gives a self-contained presentation of its foundations. The central notion here is that of a polymorphism of relational structure. Whereas the notions of an automorphism and an endomorphism are very well established and much used in mathematics, and in model theory in particular, the use of polymorphisms is much less common. A polymorphism is essentially a multi-dimensional version of an endomorphism - by definition, an n-ary polymorphism of a structure
$\mathbf {A}$
is a homomorphism from
$\mathbf {A}^n$
, the n-th direct power of
$\mathbf {A}$
, back to
$\mathbf {A}$
.
Two things make polymorphisms particularly useful in the context of CSPs. First, for nicely behaved structures
$\mathbf {A}$
(e.g., for all finite structures), they precisely determine what other structures can be primitively positively (pp-)defined or pp-interpreted in
$\mathbf {A}$
. For such structures, the polymorphisms of
$\mathbf {A}$
determine the complexity of
$\mathrm {CSP}(\mathbf {A})$
, which gives a convenient grouping of the structures into classes with the same complexity of
$\mathrm {CSP}(\mathbf {A})$
. Second, the set of all polymorphisms of a structure forms a clone (i.e., it is closed under composition), and in this way one can associate a universal algebra to every structure. One can then use the theory of universal algebras, which provides a language and the means to reason about the structure of the relations pp-definable in
$\mathbf {A}$
, and thus about the complexity of
$\mathrm {CSP}(\mathbf {A})$
. The case when
$\mathbf {A}$
is finite is particularly well understood by now, through a deep theory of finite universal algebras, some of which was developed before, and some specifically with the resolution of the Feder–Vardi conjecture in mind. The full proof of this conjecture is beyond the scope of this book, though.
CSPs for general (not necessarily finite) structures
$\mathbf {A}$
can behave wildly. In order for even the basics of the algebraic approach to work, one has to restrict the class of infinite structure under consideration. This is where model theory provides the tools and the guidance. The main focus of the book is on using model theory to identify classes of structures (which contain all finite structures as well as many infinite structures arising in applications), where the algebraic approach works in that (a) the polymorphisms fully determine the complexity of CSPs and, also, preferably, (b) there are useful tools to analyse polymorphisms in order to perform the complexity analysis of CSPs, especially when there is a reasonable hope to obtain a complete complexity dichotomy.
The class of
$\omega $
-categorical structures plays a very important role in the book, which provides a very thorough treatment of this class, focusing particularly on aspects that are useful for the analysis of the complexity of CSPs. The foundations of the algebraic approach are then presented in the context of this class of structures. It turns out, however, that the class of
$\omega $
-categorical structures is still too rich to hope for a dichotomy for the corresponding CSPs. The book has a chapter about classes of structures where such a dichotomy cannot be expected, and in particular some
$\omega $
-categorical structures appear there. Bodirsky and Pinsker conjectured that a dichotomy holds for a specific subclass of
$\omega $
-categorical structures, namely, first-order reducts of finitely bounded homogeneous structures, whose CSPs are always in
$\text {NP}$
. This conjecture, and its many equivalent forms, is one of the focal points of the book.
The book presents two specific study cases: equality CSPs and temporal CSPs, where templates are first-order reducts of
$(\mathbb {N},=)$
and
$(\mathbb {Q},<)$
, respectively. The author demonstrates, with full proofs, how the algebraic approach is applied to prove the Bodirsky–Pinsker conjecture in each case.
