The Complexity of Plan Existence and Evaluation in Probabilistic Domains
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, NPPP, co-NP PP, and PSPACE. Of these, the probabilistic classes PP and NPPP 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.
Cite
Text
Goldsmith et al. "The Complexity of Plan Existence and Evaluation in Probabilistic Domains." Conference on Uncertainty in Artificial Intelligence, 1997.Markdown
[Goldsmith et al. "The Complexity of Plan Existence and Evaluation in Probabilistic Domains." Conference on Uncertainty in Artificial Intelligence, 1997.](https://mlanthology.org/uai/1997/goldsmith1997uai-complexity/)BibTeX
@inproceedings{goldsmith1997uai-complexity,
title = {{The Complexity of Plan Existence and Evaluation in Probabilistic Domains}},
author = {Goldsmith, Judy and Littman, Michael L. and Mundhenk, Martin},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {1997},
pages = {182-189},
url = {https://mlanthology.org/uai/1997/goldsmith1997uai-complexity/}
}