  We examine the computational complexity of testing and finding small plans in
probabilistic planning domains with both flat and propositional
representations. The complexity of plan evaluation and existence varies with
the plan type sought; we examine totally ordered plans, acyclic plans, and
looping plans, and partially ordered plans under three natural 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-NP^PP, and PSPACE. In the
process of proving that certain planning problems are complete for NP^PP, we
introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the
standard Boolean satisfiability problem to computations involving probabilistic
quantities; our results suggest that the development of good heuristics for
E-MAJSAT could be important for the creation of efficient algorithms for a wide
variety of problems.
