Refining complexity analyses in planning by exploiting the exponential time hypothesis
2016 (English)In: Annals of Mathematics and Artificial Intelligence, ISSN 1012-2443, E-ISSN 1573-7470, Vol. 78, no 2, 157-175 p.Article in journal (Refereed) Published
The use of computational complexity in planning, and in AI in general, has always been a disputed topic. A major problem with ordinary worst-case analyses is that they do not provide any quantitative information: they do not tell us much about the running time of concrete algorithms, nor do they tell us much about the running time of optimal algorithms. We address problems like this by presenting results based on the exponential time hypothesis (ETH), which is a widely accepted hypothesis concerning the time complexity of 3-SAT. By using this approach, we provide, for instance, almost matching upper and lower bounds onthe time complexity of propositional planning.
Place, publisher, year, edition, pages
SPRINGER , 2016. Vol. 78, no 2, 157-175 p.
Action planning; Computational complexity; Lower bounds; Upper bounds; Exponential time hypothesis
IdentifiersURN: urn:nbn:se:liu:diva-131654DOI: 10.1007/s10472-016-9521-yISI: 000382884300003OAI: oai:DiVA.org:liu-131654DiVA: diva2:1014972
Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Swedish Research Council (VR) [621-2014-4086]2016-10-032016-09-302016-10-03