Knowledge compilation has been successfully used to solve beyond NP problems, including some PP-complete and NPPP-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 NPPP and includes interesting AI problems, such as non-myopic value of information. We show how to solve the prototypical PPPP-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 PPPPP-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.

The sentential decision diagram (SDD) has been recently proposed as a new tractable representation of Boolean functions that generalizes the influential ordered binary decision diagram (OBDD). Empirically, compiling CNFs into SDDs has yielded significant improvements in both time and space over compiling them into OBDDs, using a bottom-up compilation approach. In this work, we present a top-down CNF to SDD compiler that is based on techniques from the SAT literature. We compare the presented compiler empirically to the state-of-the-art, bottom-up SDD compiler, showing orders-of-magnitude improvements in compilation time.