We present algebraic conditions on constraint languages Г that ensure the hardness of the constraint satisfaction problem CSP(Г) for complexity classes L, NL, P, NP and Mod{sub}pL. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP(Г) 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 CSP. The results pave the way for a refinement of the dichotomy conjecture stating that each CSP(Г) 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 CSP. We also infer a partial classification theorem for the complexity of CSP(Г) when the associated algebra of Г is the full idempotent reduct of a preprimal algebra.
展开▼
