Refining complexity analyses in planning by exploiting the exponential time hypothesis

DOI10.1007/S10472-016-9521-YMaRDI QIDQ504223zbMATH OpenOpenAlexWikidataFDO

Authors Meysam Aghighi, Christer Bäckström, Peter Jonsson, Simon Ståhlberg

Publication date 25 January 2017

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-131654

zbMATH Keywords

computational complexitylower boundsexponential time hypothesisupper boundsaction planning

Mathematics Subject Classification ID

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

Recommendations

• Analysing approximability and heuristics in planning using the exponential-time hypothesis
• Complexity results for standard benchmark domains in planning
• On the computational complexity of temporal projection, planning, and plan validation
• A complete parameterized complexity analysis of bounded planning
• Computational complexity of planning and approximate planning in the presence of incompleteness
• Complexity results for HTN planning
• Complexity of timeline-based planning over dense temporal domains: exploring the middle ground
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• The influence of k-dependence on the complexity of planning
• Understanding planning tasks. Domain complexity and heuristic decomposition

Cites work

• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 6519681 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A complete parameterized complexity analysis of bounded planning
• A refined view of causal graphs and component sizes: SP-closed graph classes and beyond
• Algorithms and limits for compact plan representations
• An Isomorphism Between Subexponential and Parameterized Complexity Theory
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• Complexity results for standard benchmark domains in planning
• Deterministic versus nondeterministic time and lower bound problems
• Lower bounds based on the exponential time hypothesis
• On the complexity of \(k\)-SAT
• On the limits of sparsification
• Power indices and easier hard problems
• Relationships between nondeterministic and deterministic tape complexities
• Strong computational lower bounds via parameterized complexity
• The Time Complexity of Constraint Satisfaction
• The computational complexity of propositional STRIPS planning
• Tight lower bounds for certain parameterized NP-hard problems
• Tractable plan existence does not imply tractable plan generation
• Which problems have strongly exponential complexity?
• ``Distance? Who cares? Tailoring merge-and-shrink heuristics to detect unsolvability

Cited in

(6)

• Upper and lower time and space bounds for planning
• Algorithms and conditional lower bounds for planning problems
• On the computational complexity of temporal projection, planning, and plan validation
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Complexity of qualitative timeline-based planning
• Analysing approximability and heuristics in planning using the exponential-time hypothesis

This page was built for publication: Refining complexity analyses in planning by exploiting the exponential time hypothesis

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