Class Description

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.

Linked From

Δ2P: P With NP Oracle

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].

More about...


DP or Dp: Difference Polynomial-Time

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].

More about...


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.

More about...