TR07-024 Authors: Laszlo Egri, Benoit Larose, Pascal Tesson

Publication: 13th March 2007 19:51

Downloads: 3244

Keywords:

We introduce symmetric Datalog, a syntactic restriction of linear

Datalog and show that its expressive power is exactly that of

restricted symmetric monotone Krom SNP. The deep result of

Reingold on the complexity of undirected

connectivity suffices to show that symmetric Datalog queries can be

evaluated in logarithmic space. We show that for a number of

constraint languages \Gamma, the complement of the constraint

satisfaction problem CSP(\Gamma) can be expressed in symmetric

Datalog. In particular, we show that if CSP(\Gamma) is

first-order definable and \Lambda is a finite subset of the

relational clone generated by \Gamma then \neg \CSP(\Lambda) is

definable in symmetric Datalog. Over the two-element domain and

under a standard complexity-theoretic assumption, expressibility of

\neg CSP(\Gamma) in symmetric Datalog corresponds exactly to the

class of CSPs solvable in logarithmic space. Finally, we describe a

fairly general subclass of implicational (or 0/1/all) constraints

for which the complement of the corresponding CSP is also definable

in symmetric Datalog. Our results provide preliminary evidence that

symmetric Datalog may be a unifying explanation for families of CSPs

lying in L.