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].
A level of PH, the polynomial hierarchy.
One Δ2P-complete problem: Given a Boolean formula, does the lexicographically last satisfying assignment end with a 1? [Kre88]
Contains BH.
There exists an oracle relative to which Δ2P is not contained in PP [Bei94].
There exists another oracle relative to which Δ2P is contained in P/poly [BGS75], and indeed has linear-size circuits [Wil85].
There exists an oracle B for which BPPB is exponentially more powerful than Δ2PB [KV96].
If P = NP, then any polynomial-size circuit C can be learned in Δ2P with C oracle [Aar06].
DP = BH2, the second level of the Boolean hierarchy.
The languages that are the interesction of a language in NP and a language in co-NP.
Contains NP and co-NP, is contained in Δ2P.
Complete problems: Exact-Clique, SAT-UNSAT, etc.
Defined in [PY84].
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.