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 C₀P = P, and the (n+1)-th level is C_n+1P = PP^C_nP (i.e., PP with oracle C_n).^[2] Thus:

• C₀P = P
• C₁P = PP
• C₂P = PP^PP
• C₃P = PP^PPPP
• ...

The counting hierarchy is contained within PSPACE.^[2] By Toda's theorem, the polynomial hierarchy PH is entirely contained in P^PP,^[3] and therefore in C₂P = PP^PP.

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

• Torán, Jacobo (1991). "Complexity classes defined by counting quantifiers". Journal of the ACM. 38 (3): 753–774. doi:10.1145/116825.116858. MR 1125929.