The complexity of constraint satisfaction revisited

DOI10.1016/0004-3702(93)90170-GMaRDI QIDQ2675271zbMATH OpenOpenAlexFDO

Authors Alan K. Mackworth, Eugene C. Freuder

Publication date 21 September 2022

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(93)90170-g

Mathematics Subject Classification ID

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

Recommendations

• Constraint satisfaction problems: complexity and algorithms
• The complexity of constraint satisfaction: an algebraic approach
• Constraint satisfaction -- algorithms and complexity analysis
• Complexity of conservative constraint satisfaction problems
• Computational Complexity of Constraint Satisfaction

Cites work

• scientific article; zbMATH DE number 67482 (Why is no real title available?)
• Arc consistency for factorable relations.
• Consistency in networks of relations
• Network-based heuristics for constraint-satisfaction problems
• Networks of constraints: Fundamental properties and applications to picture processing
• On the parallel complexity of discrete relaxation in constraint satisfaction networks
• REF-ARF: A system for solving problems stated as procedures
• Tree clustering for constraint networks

Cited in

(22)

• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.
• Complexity of approximating CSP with balance / hard constraints
• Using constraint metaknowledge to reduce arc consistency computation
• The satisfiability constraint gap
• A Complexity Index for Satisfiability Problems
• The Complexity of theA B CProblem
• scientific article; zbMATH DE number 5287580 (Why is no real title available?)
• Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes
• Constraint satisfaction with bounded treewidth revisited
• The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
• Conjunctive-query containment and constraint satisfaction
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• Complexity of clausal constraints over chains
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Automatic generation of dominance breaking nogoods for a class of constraint optimization problems
• On the complexity of trial and error for constraint satisfaction problems
• The complexity of soft constraint satisfaction
• Combinatorial problems raised from 2-semilattices
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of problems for quantified constraints
• The complexity of constraint satisfaction problems for small relation algebras
• The Complexity of Satisfaction Problems in Reverse Mathematics

This page was built for publication: The complexity of constraint satisfaction revisited

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