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

Authors: 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}
  }