## Paper: Symmetric Datalog and Constraint Satisfaction Problems in Logspace (at LICS 2007)

**László Egri Benoit Larose Pascal Tesson**

### Abstract

We introduce symmetric Datalog, a syntactic restriction of linear Datalog and show that its expressive power is exactly that of restricted symmetric Krom monotone SNP. The deep result of Reingold [17] 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 ¬CSP(\Lambda) is definable in symmetric Datalog. Over the two-element domain and under standard complexity-theoretic assumptions, expressibility of ¬CSP(\Gamma) in symmetric Datalog corresponds exactly to the class of CSPs computable 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.

### BibTeX

@InProceedings{EgriLarose-SymmetricDatalogand, author = {László Egri and Benoit Larose and Pascal Tesson}, title = {Symmetric Datalog and Constraint Satisfaction Problems in Logspace}, booktitle = {Proceedings of the Twenty-Second Annual IEEE Symposium on Logic in Computer Science (LICS 2007)}, year = {2007}, month = {July}, pages = {193--202}, location = {Wroclaw, Poland}, publisher = {IEEE Computer Society Press} }