Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
This work provides theoretical lower bounds for exact model counting algorithms, impacting probabilistic databases and related fields, but it is incremental as it builds on existing methods and lower bounds.
The paper tackled the problem of exactly computing the number of satisfying assignments for Boolean formulas by showing that decision-DNNFs can be converted into FBDDs with quasipolynomial or polynomial size increases, leading to exponential lower bounds for decision-DNNFs and separating them from related representations like d-DNNFs and AND-FBDDs.
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-DNNF's 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.