Tradeoffs in the Complexity of Backdoor Detection

DOI10.1007/978-3-540-74970-7_20zbMath1145.68511OpenAlexW203718333MaRDI QIDQ3523063

Bistra Dilkina, Ashish Sabharwal, Carla P. Gomes

Publication date: 2 September 2008

Published in: Principles and Practice of Constraint Programming – CP 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74970-7_20

Mathematics Subject Classification ID

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

Related Items (10)

Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Backdoors to Satisfaction ⋮ Random Instances of W[2-Complete Problems: Thresholds, Complexity, and Algorithms] ⋮ Computation of Renameable Horn Backdoors ⋮ Learning cluster-based structure to solve constraint satisfaction problems ⋮ Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search ⋮ Backdoors for linear temporal logic ⋮ Backdoors into heterogeneous classes of SAT and CSP ⋮ Backdoors in the Context of Learning ⋮ Backdoors to tractable answer set programming

Uses Software

• Chaff

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Backdoor sets for DLL subsolvers
• Network-based heuristics for constraint-satisfaction problems
• Detecting embedded Horn structure in propositional logic
• Heavy-tailed phenomena in satisfiability and constraint satisfaction problems
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• Constraint Satisfaction with Bounded Treewidth Revisited
• A sufficient condition for backtrack-bounded search
• A Sufficient Condition for Backtrack-Free Search
• On the minimality and global consistency of row-convex constraint networks
• Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in SAT-Based Planning

This page was built for publication: Tradeoffs in the Complexity of Backdoor Detection