Judy Goldsmith and Robert H. Sloan
We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Interval MDP is coNPPP-hard. In particular, the test for e -homogeneity, a necessary part of verifying any proposed partition, is coNPPP-complete. This indicates that, without further assumptions on the sorts of partitioning allowed or the structure of the original propositional MDP, this is not likely to be a practical approach. We also analyze the complexity of finding the minimal-size partition, and of the k -block partition existence problem. Finally, we show that the test for homogeneity ofan exact partition is complete for coNPC- P, which is the same class as coNPPP. All of this analysis applies equally well to the process of partitioning the state space via Structured Value Iteration.