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. It has been shown[1] that a collapse of the boolean hierarchy would imply a collapse of the polynomial hierarchy.
Formal definition
BH is defined as follows:[2]
- 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
Derived classes
- DP (Difference Polynomial Time) is BH2.[3]
References
- ^ 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
 | This computer science article is a stub. You can help Wikipedia by expanding it. |