Theory of Computational Complexity, 2nd Edition

Chapter 9

Complexity of Counting

How do I love thee? Let me count the ways.

I love thee to the depth and breadth and height

My soul can reach.

—Elizabeth Barrett Browning

Informally, the complexity class NP contains the decision problems in which an input instance is accepted if and only if there exists a good witness. The complexity classes PP and BPP contain the problems in which an input instance is accepted if and only if the majority of the witnesses are good. All these problems are just the restricted forms of a more general counting problem: for any input instance, count the number of good witnesses for it. Such counting problems occur very often in practical problems. For instance, for the HAMILTONIAN CIRCUIT problem, one is often interested not only in the existence of a Hamiltonian circuit in a graph but also interested in the total number of different Hamiltonian circuits. In this chapter, we study the complexity of these counting problems and its relation to the complexity of nondeterministic and probabilistic computation. We define two complexity classes, #P and , of counting problems. The main result of this chapter shows that decision problems in the polynomial-time hierarchy are polynomial-time reducible to counting problems in these complexity classes. We also investigate the relation between the relativized #P and the relativized polynomial-time hierarchy. ...