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

clonecomputational complexityconstraint satisfactionGalois connectionpolymorphismsatisfiability problems

Mathematics Subject Classification ID

Logic in computer science (03B70) Applications of universal algebra in computer science (08A70) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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)

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

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)