Alexandr Kazda, Vanderbilt University
“What would symmetric Datalog do?”
We will talk about a class of Constraint Satisfaction Problems (CSPs) that can be solved in deterministic logarithmic space using fragments of the Datalog language. Datalog language is a close relative to the more famous Prolog programming language; Datalog programs for CSP can be evaluated in polynomial time, and fragments of Datalog are even less computationally demanding: evaluating so-called linear Datalog can be done in nonderministic logspace, while symmetric Datalog programs only need deterministic logspace to run. We give a brief overview of what does it mean to solve CSP using Datalog, followed by an attempt to characterize relational structures A such that CSP(A) can be solved by symmetric Datalog.