The complexity of constraint satisfaction revisited

DOI10.1016/0004-3702(93)90170-GOpenAlexW2012694101MaRDI QIDQ2675271FDOQ2675271

Eugene C. Freuder, Alan K. Mackworth

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

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

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)

Cites Work

• Consistency in networks of relations
• Network-based heuristics for constraint-satisfaction problems
• Networks of constraints: Fundamental properties and applications to picture processing
• Tree clustering for constraint networks
• On the parallel complexity of discrete relaxation in constraint satisfaction networks
• Title not available (Why is that?)
• REF-ARF: A system for solving problems stated as procedures
• Arc consistency for factorable relations.

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
• A Complexity Index for Satisfiability Problems
• The satisfiability constraint gap
• The Complexity of theA B CProblem
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Complexity of clausal constraints over chains
• Automatic generation of dominance breaking nogoods for a class of constraint optimization problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• 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 Satisfaction Problems in Reverse Mathematics
• The complexity of constraint satisfaction problems for small relation algebras

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)