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

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>