TR07-025 Authors: Benoit Larose, Pascal Tesson, Pascal Tesson

Publication: 13th March 2007 19:52

Downloads: 2887

Keywords:

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.