Lectures take place at the Institute of Mathematics and Statistics, No.8 building within the Faculty of Science, Kotlarska 2, Brno

Wednesday, November 20, 2013, at 5:00 p.m. in M6

Libor Barto
The dichotomy for constraint satisfaction problems

Abstract:

The constraint satisfaction problem (CSP) provides a common framework for many theoretical problems in computer science as well as for many real-life applications. An instance of the CSP consists of a number of variables and constraints imposed on them and the objective can be

(1) to determine whether variables can be evaluated in such a way that all the constraints are satisfied,

(2) to maximise the number of satisfied constraints,

(3) to count all satisfactory assignments, etc. The CSP can also be expressed in terms of conjuctive formulas, or in terms of homomorphisms between relational structures.

Most of the questions about general CSP are computationally hard, however certain natural restrictions on the form of the constraints can ensure tractability. I will talk about so called non-uniform finite domain CSPs - the same problem, but the set of allowed constraint relations is fixed to a set of relations on a finite set. Examples of decision problems of this sort include Graph k-colorability, Graph reachability, k-SAT, Linear equations over a finite field, and many others. I will discuss examples of CSPs and show some of the recent progress on the computational complexity of non-uniform CSPs.