Class Description

QH: Query Hierarchy Over NP

QH_k is defined to be P^NP[k]; that is, P with k queries to an NP oracle (where k is a constant). Then QH is the union of QH_k 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:

• BH₁ = NP.
• BH_2i is the class of languages that are the intersection of a BH_2i-1 language with a coNP language.
• BH_2i+1 is the class of languages that are the union of a BH_2i language with an NP language.

Then BH is the union over all i of BH_i.

Defined in [WW85].

For more detail see [CGH+88].

Contained in Δ₂P and indeed in P^NP[log].

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

See also: DP, QH.

More about...