DNF Counting and the Monte Carlo Method
A DNF formula is a disjunction (OR) of clauses; a clause is a conjunction (AND) of literals; a literal is a variable or its negation. For example,
\[
(x_1 \wedge x_2 \wedge \overline{x_3}) \vee (x_1 \wedge \overline{x_4}) \vee (x_3 \wedge x_4 \wedge x_5 \wedge \overline{x_6}).
\]
The DNF counting problem is to compute the number of satisfying assignments for a DNF formula. This problem is #P-complete. It is equivalent to the CNF counting problem. Note that, the DNF satisfiability problem is easy, while CNF satisfiability is NP-complete.
Monte Carlo Algorithms
Let F be a DNF formula with n variables. Consider the following simple randomized algorithm. Randomly generate N assignments and count the number of assignments satisfying F; denote this count by M. Then output the estimation
\[
\frac{M}{N} \cdot 2^n.
\]
If the total number of satisfying assignment is close to \(2^n\), then the above estimation is good. However, if there are very few satisfying assignments, it turns out the number of samples N needs to be exponentially large to get a good estimation. Consider the following improved algorithm.
For each clause \(C_i\), let \(S_i\) be the collection of assignments satisfying it. Then we define a probability
\[
p_i = \frac{|S_i|}{ \sum_{j=1}^{n} |S_j|}.
\]
The algorithm works as below. We run the sampling for N times. Each time, pick up a clause \(C_i\) with probability \(p_i\), and then pick up an assignment from \(S_i\). Check whether this assignment satisfies F. Finally, count the number of satisfying samples; denote the count by M. Then we output the estimate
\[
\frac{M}{N} \cdot \sum_{j=1}^{n} |S_j|.
\]
This algorithm is particularly efficient even when the number of satisfying assignments is small.