In complexity theory, the counting hierarchy is a hierarchy of complexity classes. It is analogous to the polynomial hierarchy, but with NP replaced with PP. It was defined in 1986 by Klaus Wagner.
More precisely, the zero-th level is C<sub>0</sub>P = P, and the (n+1)-th level is C<sub>n+1</sub>P = PP<sup>C<sub>n</sub>P</sup> (i.e., PP with oracle C<sub>n</sub>). Thus:
The counting hierarchy is contained within PSPACE. By Toda's theorem, the polynomial hierarchy PH is entirely contained in P<sup>PP</sup>, and therefore in C<sub>2</sub>P = PP<sup>PP</sup>.