In complexity theory, the counting hierarchy is a

hierarchy A hierarchy (from Ancient Greek, Greek: , from , 'president of sacred rites') is an arrangement of items (objects, names, values, categories, etc.) that are represented as being "above", "below", or "at the same level as" one another. Hierarchy ...

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

es. It is analogous to the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...

, but with NP replaced with PP. It was defined in 1986 by Klaus Wagner. More precisely, the zero-th level is C₀P = P, and the (''n''+1)-th level is C_''n''+1P = PP^C_''n''P (i.e., PP with

oracle An oracle is a person or thing considered to provide insight, wise counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. If done through occultic means, it is a form of divination. Descript ...

C_''n''). Thus: * C₀P = P * C₁P = PP * C₂P = PP^PP * C₃P = PP^{PP^PP} * ... The counting hierarchy is contained within

PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can ...

. By Toda's theorem, the

PH is entirely contained in P^PP, and therefore in C₂P = PP^PP.

References

Further reading