The Complexity of Plan Existence and Evaluation in Probabilistic Domains

Judy Goldsmith
Dept. of Computer Science
University of Kentucky
Lexington, KY 40506-0046
goldsmit@cs.uky.edu

Michael L. Littman
Dept. of Computer Science
Duke University
Durham, NC 27708-0129
mlittman@cs.duke.edu

Martin Mundhenk
FB4 - Theoretische Informatik
Universitat Trier
D-54286 Trier
Germany
mundhenk@ti.uni-trier.de

ABSTRACT

We examine the computational complexity of testing and finding small
plans in probabilistic planning domains with succinct representations.
We find that many problems of interest are complete for a variety of
complexity classes: NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE.  Of
these, the probabilistic classes PP and NP^PP are likely to be of
special interest in the field of uncertainty in artificial
intelligence and are deserving of additional study.  These results
suggest a fruitful direction of future algorithmic development.