ECCC-Report TR07-025https://eccc.weizmann.ac.il/report/2007/025Comments and Revisions published for TR07-025en-usTue, 13 Mar 2007 19:52:08 +0200
Paper TR07-025
| Universal Algebra and Hardness Results for Constraint Satisfaction Problems |
Benoit Larose,
Pascal Tesson,
Pascal Tesson
https://eccc.weizmann.ac.il/report/2007/025We 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.
Tue, 13 Mar 2007 19:52:08 +0200https://eccc.weizmann.ac.il/report/2007/025