The complexity of maximal constraint languages

DOI10.1145/380752.380868MaRDI QIDQ5176025zbMATH OpenOpenAlexFDO

Authors Andrei A. Bulatov, Andrei Krokhin, P. Jeavons

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380868

zbMATH Keywords

algebraic invariance propertycomplexityconstraint languageconstraint satisfaciton problemNP-completenessrelational clonetractability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Maximal Infinite-Valued Constraint Languages
• Maximal infinite-valued constraint languages
• scientific article; zbMATH DE number 1670830
• STACS 2005
• Classifying the Complexity of Constraints Using Finite Algebras

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(22)

• Existentially restricted quantified constraint satisfaction
• Maximal infinite-valued constraint languages
• The complexity of soft constraint satisfaction
• Combinatorial problems raised from 2-semilattices
• Tractability in constraint satisfaction problems: a survey
• The Complexity of Equality Constraint Languages
• A Galois connection for valued constraint languages of infinite size
• Necessary conditions for tractability of valued CSPs
• On minimal constraint networks
• The Complexity of Minimal Inference Problem for Conservative Constraint Languages
• Rigid binary relations on a 4-element domain
• Classifying the Complexity of Constraints Using Finite Algebras
• Tractable structures for constraint satisfaction with truth tables
• Maximal Infinite-Valued Constraint Languages
• Basics of Galois Connections
• Introduction to the Maximum Solution Problem
• scientific article; zbMATH DE number 5499325 (Why is no real title available?)
• STACS 2005
• Recognizing frozen variables in constraint satisfaction problems
• The expressive rate of constraints
• Periodic constraint satisfaction problems: Tractable subclasses
• The complexity of equality constraint languages

This page was built for publication: The complexity of maximal constraint languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176025)