Class Description

QH: Query Hierarchy Over NP

QHk is defined to be PNP[k]; that is, P with k queries to an NP oracle (where k is a constant). Then QH is the union of QHk over all nonnegative k.

QH = BH [Wag88]; thus, either both hierarchies are infinite or both collapse to some finite level.

Linked From

BH: Boolean Hierarchy Over NP

The smallest class that contains NP and is closed under union, intersection, and complement.

The levels are defined as follows:

Then BH is the union over all i of BHi.

Defined in [WW85].

For more detail see [CGH+88].

Contained in Δ2P and indeed in PNP[log].

If BH collapses at any level, then PH collapses to Σ3P [Kad88].

See also: DP, QH.

More about...