# 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. A collapse of the boolean hierarchy would imply a collapse of the polynomial hierarchy.^{[1]}

## Formal definition

BH is defined as follows:^{[2]}

- BH
_{1}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 (Difference Polynomial Time) is BH
_{2}.^{[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.

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

Alternatively,^{[5]} 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 {*x*_{1}, ... *x _{m}*} of instances of A such that

*x*∈ A implies

_{i}*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*∈ A is odd or even:

_{i}^{[4]}

- BH
_{2k}-hardness is proved if and the number of*x*∈ A is odd_{i} - BH
_{2k+1}-hardness is proved if and the number of*x*∈ A is even_{i}

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

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.