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:
|This computer science article is a stub. You can help Wikipedia by expanding it.|
Here you can share your comments or contribute with more information, content, resources or links about this topic.