# 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[edit]

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 the BH
_{i}

## Derived classes[edit]

- DP (Difference Polynomial Time) is BH
_{2}.^{[3]}

## Equivalent definitions[edit]

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[edit]

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)]}.

## References[edit]

**^**Chang, R.; Kadin, J. (1996). "The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection".*SIAM J. Comput.***25**(25): 340–354. CiteSeerX 10.1.1.77.4186. doi:10.1137/S0097539790178069.**^***Complexity Zoo*: Class BH**^***Complexity Zoo*: Class DP- ^
^{a}^{b}Wagner, K. (1987). "More Complicated Questions About Maxima and Minima, and Some Closures of NP".*Theoret. Comput. Sci.***51**: 53–80. doi:10.1016/0304-3975(87)90049-1. **^**Riege, T.; Rothe, J. (2006). "Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey".*J. Univers. Comput. Sci.***12**(5): 551–578.

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