liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Inngår i: Annals of Mathematics and Artificial Intelligence, ISSN 1012-2443, E-ISSN 1573-7470, Vol. 78, nr 2, s. 157-175Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
SPRINGER , 2016. Vol. 78, nr 2, s. 157-175
Emneord [en]
Action planning; Computational complexity; Lower bounds; Upper bounds; Exponential time hypothesis
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-131654DOI: 10.1007/s10472-016-9521-yISI: 000382884300003OAI: oai:DiVA.org:liu-131654DiVA, id: diva2:1014972
Merknad

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

Tilgjengelig fra: 2016-10-03 Laget: 2016-09-30 Sist oppdatert: 2018-01-14

Open Access i DiVA

fulltext(352 kB)94 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 352 kBChecksum SHA-512
118e37325173954fef571182be12f68384b74e9c5e6e38ce8a334995f235c39d08e62beb3753e1fffefff14aadb48a128205b86a8c7de1b5426d3f5a9fa604cf
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekst

Søk i DiVA

Av forfatter/redaktør
Aghighi, MeysamBäckström, ChristerJonsson, PeterStåhlberg, Simon
Av organisasjonen
I samme tidsskrift
Annals of Mathematics and Artificial Intelligence

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 94 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 436 treff
RefereraExporteraLink to record
Permanent link

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