Universal algebra and hardness results for constraint satisfaction problems

We present algebraic conditions on constraint languages Γ that ensure the hardness of the constraint satisfaction problem for complexity classes L, NL, P, NP and ModpL. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if is not first-order definable then it is L-hard. Our proofs rely on tame congruence theory and on a fine-grain analysis of the complexity of reductions used in the algebraic study of . The results pave the way for a refinement of the dichotomy conjecture stating that each lies in P or is NP-complete and they match the recent classification of [E. Allender, M. Bauland, N. Immerman, H. Schnoor, H. Vollmer, The complexity of satisfiability problems: Refining Schaefer’s theorem, in: Proc. 30 th Math. Found. of Comp. Sci., MFCS’05, 2005, pp. 71–82] for Boolean . We also infer a partial classification theorem for the complexity of when the associated algebra of Γ is the full idempotent reduct of a preprimal algebra.