We present algebraic conditions on constraint languages \Gamma that ensure the hardness of the constraint satisfaction problem CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP(\Gamma) is not first-order definable then it ... more >>>

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 ... more >>>