Constraint Satisfaction, Complexity, and Algebra

The constraint satisfaction problem, or CSP in short, provides a unifying framework in which it is possible to express, in a natural way, a wide variety of algorithmic problems, including propositional satisfiability, graph colourability, systems of equations. An instance of CSP consists of a set of variables, a set of values for the variables, and a set of constraints that restrict the combinations of values that certain subsets of variables may take. Given such an instance, the aim is to determine whether there is an assignment of values to the variables so that every constraint is satisfied and to find such an assignment if one exists. This is the decision version of CSP, while in the optimisation version of CSP the aim is to find an assignment that satisfying a maximum number of constraints. Since the CSP is NP-hard in general, researchers have toiled for the past thirty years to delineate the boundary between tractability and intractability for this problem. In this course, I will describe how universal algebra and lattice theory help in this effort. Lectures 1-3 will be devoted to the complexity classification problem for the decision CSP. They will contain general theory of the algebraic approach to CSP, examples and applications to problems in graph theory and logic, and an exposition of the extremely fruitful cross-fertilisation between CSP and universal algebra, including some very recent powerful results. In Lecture 4, I will show how notions from lattice theory can be used to study a similar classification problem for the optimisation version of the CSP.