Tradeoffs in the Complexity of Backdoor Detection
From MaRDI portal
Publication:3523063
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
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
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
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
