Lower bounds for exact model counting and applications in probabilistic databases


Conference Paper

The best current methods for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas can be seen, either directly or indirectly, as building decision-DNNF (decision decomposable negation normal form) representations 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 converted 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 representation size in general, and with only a polynomial increase in size in the special case of monotone k-DNF formulas. Leveraging known exponential lower bounds for FBDDs, we then obtain similar exponential lower bounds for decision-DNNFs which provide lower bounds for the recent algorithms. We also separate the power of decision-DNNFs from d-DNNFs and a generalization of decision-DNNFs known as AND-FBDDs. Finally we show how these imply exponential lower bounds for natural problems associated with probabilistic databases.

Duke Authors

Cited Authors

  • Beame, P; Li, J; Roy, S; Suciu, D

Published Date

  • November 28, 2013

Published In

  • Uncertainty in Artificial Intelligence Proceedings of the 29th Conference, Uai 2013

Start / End Page

  • 52 - 61

Citation Source

  • Scopus