Boolean hierarchy

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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]

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

  • DP (Difference Polynomial Time) is BH2.[3]

References[edit]

  1. ^ Richard Chang and Jim Kadin, The Boolean Hierarchy and the Polynomial Hierarchy: a Closer Connection
  2. ^ http://complexity-zoo.net/Complexity_Zoo:B#bh
  3. ^ http://complexity-zoo.net/Complexity_Zoo:D#dp