Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-025 | 5th March 2007 00:00

Universal Algebra and Hardness Results for Constraint Satisfaction Problems


Authors: Benoit Larose, Pascal Tesson, Pascal Tesson
Publication: 13th March 2007 19:52
Downloads: 1260


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.

ISSN 1433-8092 | Imprint