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. ...

Start Free Trial

No credit card required