THE COMPUTATIONAL-COMPLEXITY OF PROBABILISTIC PLANNING

We examine the computational complexity of testing and finding small p lans in probabilistic planning domains with both at and propositional representations. The complexity of plan evaluation and existence varie s with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three nat ural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP PP, co-NPPP, and PSPACE. In the process of proving that certain planni ng problems are complete for NP PP, we introduce a new basic NPPP-comp lete problem, E-MAJSAT, which generalizes the standard Boolean satisfi ability problem to computations involving probabilistic quantities; ou r results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wid e variety of problems.