Symmetric Datalog and constraint satisfaction problems in logspace

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 [171 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 IF, 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 A is a finite subset of the relational clone generated by F then -> CSP(Lambda) is definable in symmetric Datalog. Over the two-element domain and under standard complexity-theoretic assumptions, expressibility of -> CSP(Lambda) 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 explanationforfamilies of CSPs lying in L.