Solving PP PP -Complete Problems Using Knowledge Compilation

Knowledge compilation has been successfully used to solve beyond NP problems, including some PP-complete and NP PP -complete problems for Bayesian networks. In this work we show how knowledge compilation can be used to solve problems in the more intractable complexity class PP^PP.  This class contains NP PP and includes interesting AI problems, such as non-myopic value of information. We show how to solve the prototypical PP PP -complete problem MajMajsat in linear-time once the problem instance is compiled into a special class of Sentential Decision Diagrams. To show the practical value of our approach, we adapt it to answer the Same-Decision Probability (SDP) query, which was recently introduced for Bayesian networks. The SDP problem is also PP PP P-complete. It is a value-of-information query that quantifies the robustness of threshold-based decisions and comes with a corresponding algorithm that was also recently proposed. We present favorable experimental results, comparing our new algorithm based on knowledge compilation with the state-of-the-art algorithm for computing the SDP.