Boolean hierarchy

The boolean hierarchy is the

BH is defined as follows:[2]

• BH₁ is
  NP
  .
• BH_2k is the class of languages which are the
  coNP
  .
• BH_2k+1 is the class of languages which are the
  NP
  .
• BH is the union of all the BH_i classes.

Derived classes

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

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

Hardness for classes of the Boolean hierarchy can be proved by showing a reduction from a number of instances of an arbitrary

This computer science article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e