1 Answers
The boolean hierarchy is the hierarchy of boolean combinations 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.
9 views
Answered