Refining complexity analyses in planning by exploiting the exponential time hypothesis
DOI10.1007/s10472-016-9521-yzbMath1401.68092OpenAlexW2491675908WikidataQ59460046 ScholiaQ59460046MaRDI QIDQ504223
Simon Ståhlberg, Christer Bäckström, Meysam Aghighi, Peter Jonsson
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
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 (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity results for standard benchmark domains in planning
- Strong computational lower bounds via parameterized complexity
- Tractable plan existence does not imply tractable plan generation
- The computational complexity of propositional STRIPS planning
- Which problems have strongly exponential complexity?
- A complete parameterized complexity analysis of bounded planning
- Relationships between nondeterministic and deterministic tape complexities
- Tight lower bounds for certain parameterized NP-hard problems
- A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond
- On the Limits of Sparsification
- Algorithms and Limits for Compact Plan Representations
- Deterministic versus nondeterministic time and lower bound problems
- The Time Complexity of Constraint Satisfaction
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
- Power indices and easier hard problems
- On the complexity of \(k\)-SAT
This page was built for publication: Refining complexity analyses in planning by exploiting the exponential time hypothesis
