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.{{r|wagner|zoo}}

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).{{r|zoo}} Thus:

C₀P = P
C₁P = PP
C₂P = PP^PP
C₃P = PP^{PP^PP}
...

The counting hierarchy is contained within PSPACE.{{r|zoo}} By Toda's theorem, the polynomial hierarchy PH is entirely contained in P^PP,{{r|toda}} and therefore in C₂P = PP^PP.

References

{{reflist|refs=

{{ cite web

| url = https://complexityzoo.net/Complexity_Zoo:C#ch

| title = Complexity Zoo

| access-date = 2024-06-26

}}

{{ cite journal

| last = Wagner

| first = Klaus W.

| year = 1986

| title = The complexity of combinatorial problems with succinct input representation

| journal = Acta Informatica

| volume = 23

| pages = 325–356

| doi = 10.1007/BF00289117

}}

{{Cite journal|last=Toda|first=Seinosuke|date=October 1991|title=PP is as Hard as the Polynomial-Time Hierarchy|url=http://epubs.siam.org/doi/10.1137/0220053|journal=SIAM Journal on Computing|volume=20|issue=5|pages=865–877|doi=10.1137/0220053|issn=0097-5397|citeseerx=10.1.1.121.1246}}

}}

counting hierarchy

References

Further reading