Counting Complexity Classes

The counting complexity classes are defined in terms of the number of accepting computation paths of nondetereministic polynomial-time Turing machines. They are, therefore, the counting versions of decision problems in NP. We review the properties of well-known counting classes like #P, \PhiP, GapP, SPP etc. We also give an overview of the proof of Toda's theorem that relates the counting classes to the polynomial-time hierarchy PH. 1 Introduction The counting complexity classes correspond to counting the number of solutions to decision problems in NP. The counting version of a decision problem requires as an answer some function of the number of solutions to that problem. The counting classes are interesting also because they are also closely related to probabilistic classes like PP and BPP. A probabilistic machine accepts depending upon whether the majority of its computation paths accept or not. This notion of computation is weaker than the counting version which demands the exact ..