Boolean hierarchy

The boolean hierarchy is the hierarchy of boolean combinations (intersection, union and complementation) of NP sets. Equivalently, the boolean hierarchy can be described as the class of boolean circuits over NP predicates. It has been shown that 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 the BH_i

Derived classes

• DP (Difference Polynomial Time) is BH₂.

Equivalent definitions

Defining the conjuction and the disjunction of classes as follows allows for more compact definitions:

• C ∧ D = { A ∩ B | A ∈ C   B ∈ D }
• C ∨ D = { A ∪ B | A ∈ C   B ∈ D }

According to this definition, DP=NP ∧ coNP. The other classes of the Boolean hierarchy can be defined as follows.

$BH_{2k}=coNP\wedge B_{2k-1}$

$BH_{2k+1}=NP\vee B_{2k}$

The following equalities can be used as alterantive definitions of the classes of the Boolean hierarchy:

$BH_{2k}=\bigvee _{i=1}^{k}DP$

$BH_{2k+1}=coNP\vee \bigvee _{i=1}^{k}DP$

Alternatively, for every k ≥ 3:

$BH_{k}=DP\vee BH_{k-2}$