Class Description

CkP: kth Level of CH

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.

Linked From

CH: Counting Hierarchy

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.

More about...