Jump to content

Counting hierarchy

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Jean Abou Samra (talk | contribs) at 16:39, 26 June 2024 (←Created page with '{{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. More precisely, the zero-th level is C<sub>0</sub>P = P, and the (''n''+1)-th level is C<sub>''n''+1</sub>P...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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.

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). Thus:

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

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

References

  • "Complexity Zoo". Retrieved 2024-06-26.
  • Wagner, Klaus W. (1986). "The complexity of combinatorial problems with succinct input representation". Acta Informatica. 23: 325–356. doi:10.1007/BF00289117.

See also

Stub icon

This computer science article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Counting_hierarchy&oldid=1231128445"