The algebraic approach to CSP

Lecturer: Professor Marcin Kozik (Jagiellonian University, Cracow).

About the Lecturer | Course Summary | Slides | Assignment

About the lecturer: Dr. hab. Marcin Kozik is an Associate Professor in the Algrothmics Research Group at the Faculty of Mathematics and Computer Science of Jagiellonian University, Cracow, Poland. He obtained his PhD from Vanderbilt University in Nashville, TN, USA, where he later worked as a Visiting Professor. He also spent extended time at Charles University in Prague. He is an internationally leading figure in the theory of constraint satisfaction problems.

Course summary: The series of lectures will be devoted to the algebraic approach to The Constraint Satisfaction Problem.

A Constraint Satisfaction Problem (CSP) asks, given variables and constraints, if there is an assignment such that all the constraints are satisfied. A constraint is usually given as a list of admissible evaluations (i.e. a relation) for a tuple of variables. In 1998 Feder and Vardi introduced a concept of non-uniform CSPs: in this approach the instances of CSP are limited by a set of allowed relations - a language of CSP.

A single relation {0,1}^3\{(0,0,0),(1,1,1)} is an easy example of such a language: it defines the well-known problem monotone NAE-3SAT. In a similar way one can construct languages that define (in the terms of CSP) many of the common computational problems: 3SAT, Horn-SAT, k-colorability of graphs, solving sets of linear equations modulo p etc.

All of the problems above are in P or NP-complete. In fact the main conjecture which drives the field (postulated by Feder and Vardi) states that every finite language defines CSP which is NP-complete or in P. If the conjecture is confirmed the CSPs would form one of the largest natural classes of problems in NP which avoid problems of intermediate difficulty.

Universal algebra is a field of study which deals with algebras. An algebra is a set with a number of operations of various arities (e.g. a group). The history of universal algebra dates back to 19th century, but the contemporary research began with works of Birkhoff, Tarski and their students in 1940's. The main motivation for developing universal algebra came from logic and category theory.

The algebraic results connected to CSP are usually motivated by the book The structure of finite algebras (by McKenzie) which appeared in 1988. In this book the author points out that there are only five choices (called types 1,2,3,4,5) for a "local" behavior of a finite algebra.

An unexpected connection between these two, seemingly very different, fields of research was observed by Bulatov, Jeavons and Krokhin. Every constraint language has an associated algebra (and a family of algebras called a variety) which fully captures the complexity of the CSP. Moreover the types associated to algebras immediately give all the known hardness results: e.g. every CSP having type 1 in the variety is NP-complete. On the other hand every CSP known to be NP-complete has type 1 in the associated variety. This allows to restate the conjecture of Feder and Vardi into algebraic terms and, more importantly, postulate the classification.

The types of the algebras have deep impact on the CSP. E.g. having no types 1 and 2 is equivalent to being a complement of a language solvable (in P-time) by a DATALOG program. Having no types 1, 2 and 5 is postulated to be equivalent to solvability by linear DATALOG etc.

The connection between algebra and non-uniform CSPs is not limited to decidability. The class of robustly approximable CSPs was characterized using the types of algebras and the "quality" of the approximation is postulated to depend on the structure of the algebra. Enriching the structure of algebras with weights one can capture the complexity of Valued CSPs (VCSPs) - an optimization version of a CSP. Alternating the definitions of algebras one can capture various quantified versions of CSP.

The lecture will focus on introducing the notions and establishing the connection between the CSP and universal algebra. I will present the algorithmic principles solving wide classes of CSPs and point out the open problems. I will present the fine-grained conjectures connecting the type-set of a variety to the complexity of the CSP. Time allowing I will introduce the robust approximability and use LP and SDP relaxations of CSP to present some results, present VCSP, QCSP etc.

Assignment:

You can find the problem set here. Please send your solutions (or questions, should you have any) to Bartosz Klin by Wednesday, February 26.