Counting hierarchy
From HandWiki
Short description: Concept in computational complexity
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.
References
- ↑ Wagner, Klaus W. (1986). "The complexity of combinatorial problems with succinct input representation". Acta Informatica 23: 325–356. doi:10.1007/BF00289117.
- ↑ 2.0 2.1 2.2 "Complexity Zoo". https://complexityzoo.net/Complexity_Zoo:C#ch.
- ↑ Toda, Seinosuke (October 1991). "PP is as Hard as the Polynomial-Time Hierarchy". SIAM Journal on Computing 20 (5): 865–877. doi:10.1137/0220053. ISSN 0097-5397. http://epubs.siam.org/doi/10.1137/0220053.
Further reading
- Torán, Jacobo (1991). "Complexity classes defined by counting quantifiers". Journal of the ACM 38 (3): 753–774. doi:10.1145/116825.116858.
 |  |
