IN this chapter we apply randomization to hard counting problems. After defining the class #P, we present several #P-complete problems. We present a (randomized) polynomial time approximation scheme for the problem of counting the number of satisfying truth assignments for a DNF formula. The problem of approximate counting of perfect matchings in a bipartite graph is shown to be reducible to that of the uniform generation of perfect matchings. We describe a solution to the latter problem using the rapid mixing property of a suitably defined random walk, provided the input graph is sufficiently dense. We conclude with an overview of the estimation of the volume of a convex body.

We say that a decision problem Π is in NP if for any YES-instance I of Π, there exists a proof that I is a YES-instance that can be verified in polynomial time. Equivalently, we can cast the decision problem as a language recognition problem, where the language consists of suitable encodings of all YES-instances of Π. A proof now certifies the membership in the language of an encoded instance of the problem. Usually the proof of membership corresponds to a "solution” to the search version of the decision problem II: for instance, if II were the problem of deciding whether a given graph is Hamiltonian, a possible proof of this for a Hamiltonian graph (YES-instance) would be a Hamiltonian cycle in the graph. In the counting version of this problem, we wish to compute the number of proofs that an instance / is a YES-instance.