Refining complexity analyses in planning by exploiting the exponential time hypothesis
DOI10.1007/S10472-016-9521-YzbMATH Open1401.68092OpenAlexW2491675908WikidataQ59460046 ScholiaQ59460046MaRDI QIDQ504223FDOQ504223
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)
Full work available at URL: http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-131654
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Which problems have strongly exponential complexity?
- Relationships between nondeterministic and deterministic tape complexities
- Lower bounds based on the exponential time hypothesis
- On the complexity of \(k\)-SAT
- The computational complexity of propositional STRIPS planning
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- The Time Complexity of Constraint Satisfaction
- Strong computational lower bounds via parameterized complexity
- On the limits of sparsification
- Tight lower bounds for certain parameterized NP-hard problems
- Title not available (Why is that?)
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Tractable plan existence does not imply tractable plan generation
- A refined view of causal graphs and component sizes: SP-closed graph classes and beyond
- A complete parameterized complexity analysis of bounded planning
- Algorithms and limits for compact plan representations
- Deterministic versus nondeterministic time and lower bound problems
- ``Distance? Who cares? Tailoring merge-and-shrink heuristics to detect unsolvability
- Power indices and easier hard problems
- Complexity results for standard benchmark domains in planning
Cited In (6)
- Analysing approximability and heuristics in planning using the exponential-time hypothesis
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Complexity of qualitative timeline-based planning
- 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
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)
