The Complexity of Plan Existence and Evaluation in Probabilistic Domains

02/06/2013
by   Judy Goldsmith, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset