Polynomial-length planning spans the polynomial hierarchy

Hudson Turner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

32 Scopus citations


This paper presents a family of results on the computational complexity of planning: classical, conformant, and conditional with full or partial observability. Attention is restricted to plans of polynomially-bounded length. For conditional planning, restriction to plans of polynomial size is also considered. For this analysis, a planning domain is described by a transition relation encoded in classical propositional logic. Given the widespread use of satisfiability-based planning methods, this is a rather natural choice. Moreover, this allows us to develop a unified representation—in second-order propositional logic—of the range of planning problems considered. By describing a wide range of results within a single framework, the paper sheds new light on how planning complexity is affected by common assumptions such as nonconcurrency, determinism and polynomial-time decidability of executability of actions.

Original languageEnglish (US)
Title of host publicationLogics in Artificial Intelligence - 8th European Conference, JELIA 2002, Proceedings
EditorsSergio Flesca, Sergio Greco, Giovambattista Ianni, Nicola Leone
PublisherSpringer Verlag
Number of pages14
ISBN (Print)3540441905, 9783540441908, 9783540457572
StatePublished - 2002
Event8th European Conference on Logics in Artificial Intelligence, JELIA 2002 - Cosenza, Italy
Duration: Sep 23 2002Sep 26 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other8th European Conference on Logics in Artificial Intelligence, JELIA 2002


Dive into the research topics of 'Polynomial-length planning spans the polynomial hierarchy'. Together they form a unique fingerprint.

Cite this