Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in SAT-Based Planning

DOI10.2168/LMCS-3(1:6)2007zbMath1128.68093OpenAlexW2950188036MaRDI QIDQ5310682

Jörg Hoffmann, Bart Selman, Carla P. Gomes

Publication date: 11 October 2007

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2168/lmcs-3(1:6)2007

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 (3)

Tradeoffs in the Complexity of Backdoor Detection ⋮ Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search ⋮ Backdoor sets of quantified Boolean formulas

Uses Software

• MiniSat
• SymChaff
• IPC-4
• Walksat
• Graphplan

This page was built for publication: Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in SAT-Based Planning