Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Refining complexity analyses in planning by exploiting the exponential time hypothesis
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
2016 (Engelska)Ingår i: Annals of Mathematics and Artificial Intelligence, ISSN 1012-2443, E-ISSN 1573-7470, Vol. 78, nr 2, 157-175 s.Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
SPRINGER , 2016. Vol. 78, nr 2, 157-175 s.
Nyckelord [en]
Action planning; Computational complexity; Lower bounds; Upper bounds; Exponential time hypothesis
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:liu:diva-131654DOI: 10.1007/s10472-016-9521-yISI: 000382884300003OAI: oai:DiVA.org:liu-131654DiVA: diva2:1014972
Anmärkning

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

Tillgänglig från: 2016-10-03 Skapad: 2016-09-30 Senast uppdaterad: 2016-11-02

Open Access i DiVA

fulltext(352 kB)26 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 352 kBChecksumma SHA-512
118e37325173954fef571182be12f68384b74e9c5e6e38ce8a334995f235c39d08e62beb3753e1fffefff14aadb48a128205b86a8c7de1b5426d3f5a9fa604cf
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Aghighi, MeysamBäckström, ChristerJonsson, PeterStåhlberg, Simon
Av organisationen
Programvara och systemTekniska fakulteten
I samma tidskrift
Annals of Mathematics and Artificial Intelligence
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 26 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

Altmetricpoäng

Totalt: 71 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf