Defined as follows:
The union of the CkP's is called the counting hierarchy, CH.
Defined in [Wag86].
See [Tor91] or [AW90] for more information.
The union of the CkP's over all constant k.
Contained in PSPACE.
Strictly contains DLOGTIME-uniform TC0 [CMTV98].
It is an open problem whether there exists an oracle relative to which CH is infinite, or even unequal to PSPACE. This is closely related to the problem of whether TC0 = NC1, since a padding argument shows that TC0 = NC1 implies CH = PSPACE.