ABSTRACT
There are #P-complete counting problems that are very easy to approximate. We already discussed in Chapter 6 that an FPAUS can be given for sampling satisfying assignments of a disjunctive normal form. Since counting the satisfying assignments of a DNF is a self-reducible counting problem, we can conclude that #DNF is also in FPRAS.
