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

BH is defined as follows:^[2]

• BH₁ 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₂.^[3]

References [edit]

1. ^ Richard Chang and Jim Kadin, The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection
2. ^ http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bh
3. ^ http://qwiki.stanford.edu/index.php/Complexity_Zoo:D#dp

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