Article · Wikipedia archive · Last revised Jul 23, 2026

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.

Last revised
Jul 23, 2026
Read time
≈ 1 min
Length
163 w
Citations
5
Source
Wikipedia ↗

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

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.

References

References

  1. Wagner, Klaus W. (1986). "The complexity of combinatorial problems with succinct input representation". Acta Informatica. 23: 325–356. doi:10.1007/BF00289117.
  2. "Complexity Zoo". Retrieved 2024-06-26.
  3. Toda, Seinosuke (October 1991). "PP is as Hard as the Polynomial-Time Hierarchy". SIAM Journal on Computing. 20 (5): 865–877. CiteSeerX 10.1.1.121.1246. doi:10.1137/0220053. ISSN 0097-5397.
Further reading

Further reading