Counting hierarchy

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.[1][2]

More precisely, the zero-th level is C0P = P, and the (n+1)-th level is Cn+1P = PPCnP (i.e., PP with oracle Cn).[2] Thus:

  • C0P = P
  • C1P = PP
  • C2P = PPPP
  • C3P = PPPPPP
  • ...

The counting hierarchy is contained within PSPACE.[2] By Toda's theorem, the polynomial hierarchy PH is entirely contained in PPP,[3] and therefore in C2P = PPPP.

  1. ^ Cite error: The named reference wagner was invoked but never defined (see the help page).
  2. ^ a b c Cite error: The named reference zoo was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference toda was invoked but never defined (see the help page).