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.
BH is defined as follows:
- BH1 is NP.
- BH2k is the class of languages which are the intersection of a language in BH2k-1 and a language in coNP.
- BH2k+1 is the class of languages which are the union of a language in BH2k and a language in NP.
- BH is the union of the BHi
- DP (Difference Polynomial Time) is BH2.
- ^ Richard Chang and Jim Kadin, The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection
- ^ http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bh
- ^ http://qwiki.stanford.edu/index.php/Complexity_Zoo:D#dp