Abdundance of Negative Complexity Results

I. Domain-independent planning: PSPACE-complete or worse



(Chapman 1987; Bylander 1991; Backstrom 1993)

II. Domain-dependent planning: NP-complete or worse

(Chenoweth 1991; Gupta and Nau 1992)

III. Approximate planning: NP-complete or worse

(Selman 1994)

Previous slide

Next slide

Back to first slide

View graphic version