Department of
Applied
Mathematics

Constraint Satisfaction Problems and the Datalog language (CSI candidate talk)

Alexandr Kazda

Abstract

The Constraint Satisfaction Problem (CSP) is the problem of deciding, given two relational structures A and B, whether there exists a homomorphism from A to B. CSP is an NP-complete problem, but if we fix the target structure to B and allow only A to change, we get the problem CSP(B), whose complexity depends on B.

In this talk, we will discuss the case when CSP(B) can be solved by the Datalog programming language or its fragments, linear and symmetric Datalog. The full Datalog corresponds to CSPs solvable by local consistency checking and is well understood. However, the same can not be said about linear and symmetric Datalog. The expressive power of full Datalog is greater than that of linear Datalog which is in turn greater than the power of symmetric Datalog. As expressive power decreases, so does computational complexity: Evaluating Datalog programs is in P, while linear Datalog is in NL and symmetric Datalog is in L.

We will show that if CSP(B) is solvable by linear Datalog and B satisfies the additional algebraic condition of congruence n-permutability for some n, then CSP(B) is solvable by symmetric Datalog (and thus lies in L). This provides a good basis for future attempts to obtain a tight classification of those structures B for which CSP(B) is in NL or L.