The Limits of Knowledge Compilation for Exact Model Counting

We show limits on the efficiency of using current knowledge compilation techniques to make exact probabilistic inference for large classes of natural problems. In particular we show lower bounds on knowledge compilation to SDD and DNNF forms. DNNF representations generalize current knowledge representations used for these problems, while SDD representations are an important recent subclass of DNNF representations whose use is becoming increasingly widespread. We give the first lower bound analysis of the complexity of SDD representations by relating SDD size to best-partition communication complexity. We use this relationship to prove exponential lower bounds on the SDD size for representing a large class of problems that occur naturally as queries over probabilistic databases. We use this to derive simple examples for which SDDs must be exponentially less concise than FBDDs (read-once branching programs). Another consequence is that SDDs are not qualitatively more concise than OBDDs for representing unions of conjunctive queries. Finally, we derive exponential lower bounds on the sizes of DNNF representations using a new quasipolynomial simulation of DNNFs by nondeterministic FBDDs.