The complexity of constraint satisfaction: an algebraic approach

MaRDI QIDQ3365840zbMATH OpenFDO

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

Publication date 13 February 2006

zbMATH Keywords

constraint problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1670830
• Complexity of the counting constraint satisfaction problem
• Constraint satisfaction problems: complexity and algorithms
• Algebra and the complexity of digraph CSPs: a survey
• Computational Complexity of Constraint Satisfaction

Cited in

(35)

• Computational complexity of auditing finite attributes in statistical databases
• CSP dichotomy for special triads
• scientific article; zbMATH DE number 4162262 (Why is no real title available?)
• Tractability in constraint satisfaction problems: a survey
• Relatively quantified constraint satisfaction
• Equivariant algorithms for constraint satisfaction problems over coset templates
• Absorption in universal algebra and CSP
• Algebra and the complexity of digraph CSPs: a survey
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Closed sets of finitary functions between products of finite fields of coprime order
• CSPs with global modular constraints: algorithms and hardness via polynomial representations
• Expansions of abelian square-free groups
• The complexity of constraint satisfaction games and QCSP
• The complexity of constraint satisfaction problems for small relation algebras
• scientific article; zbMATH DE number 1670830 (Why is no real title available?)
• Constraint satisfaction problems over the integers with successor
• Complexity of the satisfiability problem for multilinear forms over a finite field
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation
• Constraint satisfaction problems: complexity and algorithms
• Majority constraints have bounded pathwidth duality
• Determining the consistency of partial tree descriptions
• Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem
• The complexity of constraint satisfaction revisited
• Dualities and algebras with a near-unanimity term
• Closed sets of finitary functions between finite fields of coprime order
• The complexity of soft constraint satisfaction
• Computational Complexity of Constraint Satisfaction
• Dualities for Constraint Satisfaction Problems
• An algebraic hardness criterion for surjective constraint satisfaction.
• The constraint satisfaction problem and universal algebra
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• On congruence lattices of algebras with an operator and the symmetric main operation
• Complexity of infinite-domain constraint satisfaction

This page was built for publication: The complexity of constraint satisfaction: an algebraic approach

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