Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-024 | 5th March 2007 00:00

Symmetric Datalog and Constraint Satisfaction Problems in Logspace


Authors: Laszlo Egri, Benoit Larose, Pascal Tesson
Publication: 13th March 2007 19:51
Downloads: 1301


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.

ISSN 1433-8092 | Imprint