On the minimal constraint satisfaction problem: complexity and generation

DOI10.1007/978-3-319-26626-8_54MaRDI QIDQ5743544zbMATH OpenOpenAlexFDO

Authors Guillaume Escamocher, Barry O'Sullivan

Publication date 5 February 2016

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-26626-8_54

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Pushing the frontier of minimality
• On minimal constraint networks
• The complexity of minimal satisfiability problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• A dichotomy theorem for constraint satisfaction problems on a 3-element set

Cites work

• A sufficient condition for backtrack-bounded search
• Consistency restoration and explanations in dynamic CSPs---Application to configuration
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• Many hard examples in exact phase transitions
• On minimal constraint networks
• The complexity of satisfiability problems

Cited in

(4)

• NP-completeness of small conflict set generation for congruence closure
• Pushing the frontier of minimality
• On minimal constraint networks
• The Complexity of Minimal Inference Problem for Conservative Constraint Languages

This page was built for publication: On the minimal constraint satisfaction problem: complexity and generation

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