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

Direct link
Referera
Referensformat
  • apa
  • 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
A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska högskolan.
2013 (engelsk)Inngår i: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 47, s. 575-611Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.

sted, utgiver, år, opplag, sider
AAAI Press, 2013. Vol. 47, s. 575-611
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-96717DOI: 10.1613/jair.3968ISI: 000322433700001OAI: oai:DiVA.org:liu-96717DiVA, id: diva2:642963
Tilgjengelig fra: 2013-08-23 Laget: 2013-08-23 Sist oppdatert: 2017-12-06

Open Access i DiVA

fulltext(541 kB)438 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 541 kBChecksum SHA-512
946015ca99117558c9d6904ba3ab3c3f68f018cc6ad9aaee583d58bd8f6016ad1b1b999e11c89ae8519d9059220c5eefc95ac215c4a182b9eedf99f9b2b5b63c
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekst

Person

Bäckström, ChristerJonsson, Peter

Søk i DiVA

Av forfatter/redaktør
Bäckström, ChristerJonsson, Peter
Av organisasjonen
I samme tidsskrift
The journal of artificial intelligence research

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 439 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: 301 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • 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