The complexity of model aggregation
Judy Goldsmith, Robert H. Sloan · 2000
We show that the problem of transforming a structured Markov decision process (MDP) into a Bounded Interval MDP is coNP PP -hard. In particular, the test for ffl-homogeneity, a necessary part of verifying any proposed partition, is coNP PP -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 of an exact partition is complete for coNP C=P , which is the same class as coNP PP . Introduction Markov decision processes (MDPs, formally defined below) are ubiquitous in AI and in the world of mathematical modeling. Related research concerns learning models and/or policies for complex systems, and developing algorithms and heuristics for planning and intelligent control....