Computational Complexity of Constraint Satisfaction

DOI10.1007/978-3-540-73001-9_80MaRDI QIDQ5425380zbMATH OpenOpenAlexFDO

Authors Heribert Vollmer

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73001-9_80

zbMATH Keywords

computational complexityconstraint satisfactionGalois connectionpolymorphismclonesatisfiability 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) Logic in computer science (03B70) Applications of universal algebra in computer science (08A70)

Recommendations

• Complexity of the counting constraint satisfaction problem
• Methods and Applications of Artificial Intelligence
• The complexity of constraint satisfaction: an algebraic approach
• Constraint satisfaction problems: complexity and algorithms
• Presenting Constraints

Cited in

(20)

• Dynamic algorithms for classes of constraint satisfaction problems
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Nonuniform Boolean constraint satisfaction problems with cardinality constraint
• A Complexity Index for Satisfiability Problems
• The property of being polynomial for Mal’tsev constraint satisfaction problems
• scientific article; zbMATH DE number 1390075 (Why is no real title available?)
• The complexity of constraint satisfaction revisited
• Constraint satisfaction problems: complexity and algorithms
• The complexity of constraint satisfaction: an algebraic approach
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• Methods and Applications of Artificial Intelligence
• Constraint satisfaction with succinctly specified relations
• Counting constraint satisfaction problems
• Constraint satisfaction problems over numeric domains
• Complexity classifications of Boolean constraint satisfaction problems
• On the complexity of trial and error for constraint satisfaction problems
• Constraint Satisfaction Parameterized by Solution Size
• Polynomial time termination and constraint satisfaction tests
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Algorithms and Computation

This page was built for publication: Computational Complexity of Constraint Satisfaction

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