A k-"DNF" formula for Boolean variables X = {x1,...,xn} can be described as = C1 C2 Cm where each Ci = (li,1 li,k). (A literal is a variable xj or xj.) So, compared to the more familiar "CNF", a DNF is "OR of ANDs" instead of "AND of ORs". Given a DNF, it is easy to check whether there is a satisfying assignment or not, because satisfying one clause is enough to satisfy the whole . So, we will be interested in estimating the number of satisfying assignments, i.e., |{f : X {T,F} : f satisfies }|. Given , let N be the true