Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Universal Algebra and Hardness Results for Constraint Satisfaction Problems
verfasst von : Benoît Larose, Pascal Tesson
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
p
L. 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 CSPs. 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 [1] for Boolean CSP. We also infer a partial classification theorem for the complexity of CSP(
Γ
) when the associated algebra of
Γ
is the idempotent reduct of a preprimal algebra.