Abstract:
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.