The complexity of constraint satisfaction: an algebraic approach

zbMATH Open1087.68107MaRDI QIDQ3365840FDOQ3365840

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

Publication date: 13 February 2006

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

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)

Cited In (35)

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

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)