Boolean hierarchy

The Boolean hierarchy is the hierarchy of Boolean combinations of NP sets. Equivalently, the Boolean hierarchy can be described as the class of Boolean circuits over NP predicates. A collapse of the Boolean hierarchy would imply a collapse of the polynomial hierarchy.

Formal definition

BH is defined as follows:

BH₁ is NP.
BH_2k is the class of languages which are the intersection of a language in BH_2k-1 and a language in coNP.
BH_2k+1 is the class of languages which are the union of a language in BH_2k and a language in NP.
BH is the union of all the BH_i classes.

Derived classes

DP is BH₂.

Equivalent definitions

Defining the conjunction and the disjunction of classes as follows allows for
more compact definitions. The conjunction of two classes contains the languages that are the intersection of a language of the first class and a language of the second class. Disjunction is defined in a similar way with the union in place of the intersection.

C ∧ D =
C ∨ D =

According to this definition, DP = NP ∧ coNP. The other classes of the Boolean hierarchy can be defined as follows.
The following equalities can be used as alternative definitions of the classes of the Boolean hierarchy:
Alternatively, for every k ≥ 3:

Hardness

Hardness for classes of the Boolean hierarchy can be proved by showing a reduction from a number of instances of an arbitrary NP-complete problem A. In particular, given a sequence of instances of A such that x_i ∈ A implies x_i-1 ∈ A, a reduction is required that produces an instance y such that y ∈ B if and only if the number of x_i ∈ A is odd or even:

BH_2k-hardness is proved if and the number of x_i ∈ A is odd
BH_2k+1-hardness is proved if and the number of x_i ∈ A is even

Such reductions work for every fixed. If such reductions exist for arbitrary, the problem is hard for P^NP.