Change search
ReferencesLink to record
Permanent link

Direct link
Refining complexity analyses in planning by exploiting the exponential time hypothesis
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
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
Abstract [en]

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.
Keyword [en]
Action planning; Computational complexity; Lower bounds; Upper bounds; Exponential time hypothesis
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-131654DOI: 10.1007/s10472-016-9521-yISI: 000382884300003OAI: oai:DiVA.org:liu-131654DiVA: diva2:1014972
Note

Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Swedish Research Council (VR) [621-2014-4086]

Available from: 2016-10-03 Created: 2016-09-30 Last updated: 2016-11-02

Open Access in DiVA

fulltext(352 kB)15 downloads
File information
File name FULLTEXT01.pdfFile size 352 kBChecksum SHA-512
118e37325173954fef571182be12f68384b74e9c5e6e38ce8a334995f235c39d08e62beb3753e1fffefff14aadb48a128205b86a8c7de1b5426d3f5a9fa604cf
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Aghighi, MeysamBäckström, ChristerJonsson, PeterStåhlberg, Simon
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Annals of Mathematics and Artificial Intelligence
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 15 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 10 hits
ReferencesLink to record
Permanent link

Direct link