Abstract:
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 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 CSPs. The results pave the way for a refinement of the dichotomy conjecture stating that each CSP(\Gamma) lies in P or is NP-complete and they match the recent classification of Allender et al. for Boolean CSP. We also infer a partial classification theorem for the complexity of CSP(\Gamma) when the associated algebra of \Gamma is the idempotent reduct of a preprimal algebra.