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

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

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

Publication date: 11 October 2007

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Backdoor sets of quantified Boolean formulas, Tradeoffs in the Complexity of Backdoor Detection

Uses Software

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