Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases∗

The best current methods for exactly com-puting the number of satisfying assignments, or the satisfying probability, of Boolean for-mulas can be seen, either directly or indi-rectly, as building decision-DNNF (decision decomposable negation normal form) repre-sentations of the input Boolean formulas. Decision-DNNFs are a special case of d-DNNFs where d stands for deterministic. We show that any decision-DNNF can be con-verted into an equivalent FBDD (free binary decision diagram) – also known as a read-once branching program (ROBP or 1-BP) – with only a quasipolynomial increase in rep-resentation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Lever-aging known exponential lower bounds for FBDDs, we then obtain similar exponen-tial lower bounds for decision-DNNFs which provide lower bounds for the recent algo-rithms. We also separate the power of decision-DNNFs from d-DNNFs and a gener-alization of decision-DNNFs known as AND-FBDDs. Finally we show how these imply exponential lower bounds for natural prob-lems associated with probabilistic databases.