Boolean hierarchy

BH is defined as follows:[2]

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

• DP (Difference Polynomial Time) is BH₂.[3]

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 = { 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.

${\displaystyle {\mathsf {BH}}_{2k}={\mathsf {coNP}}\wedge {\mathsf {BH}}_{2k-1}}$

${\displaystyle {\mathsf {BH}}_{2k+1}={\mathsf {NP}}\vee {\mathsf {BH}}_{2k}}$

The following equalities can be used as alternative definitions of the classes of the Boolean hierarchy:[4]

${\displaystyle {\mathsf {BH}}_{2k}=\bigvee _{i=1}^{k}{\mathsf {DP}}}$

${\displaystyle {\mathsf {BH}}_{2k+1}={\mathsf {NP}}\vee \bigvee _{i=1}^{k}{\mathsf {DP}}}$

Alternatively,[5] for every k ≥ 3:

${\displaystyle {\mathsf {BH}}_{k}={\mathsf {DP}}\vee {\mathsf {BH}}_{k-2}}$

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 {x₁, ... x_m} 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:[4]

• BH_2k-hardness is proved if ${\displaystyle m=2k}$ and the number of x_i ∈ A is odd
• BH_2k+1-hardness is proved if ${\displaystyle m=2k+1}$ and the number of x_i ∈ A is even

Such reductions work for every fixed k. If such reductions exist for arbitrary k, the problem is hard for P^{NP[O(log n)]}.