The Complexity of Plan Existence and Evaluation in Probabilistic Domains
This work addresses foundational complexity challenges in probabilistic planning for AI researchers, though it is incremental as it builds on existing complexity theory.
The paper investigates the computational complexity of plan existence and evaluation in probabilistic domains, finding that many problems are complete for classes like NP, PP, and PSPACE, with PP and NP^PP highlighted as particularly relevant for uncertainty in AI.
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.