Counting hierarchy
Jump to navigation
Jump to search
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
[edit | edit source]- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ a b c Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
- ^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
Further reading
[edit | edit source]- Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
 | This computer science article is a stub. You can help Wikipedia by expanding it. |