Boolean hierarchy


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.

Formal definition

BH is defined as follows:
Defining the conjunction and the disjunction of classes as follows allows for
more compact definitions. The conjunction of two classes contains the languages that are the intersection of a language of the first class and a language of the second class. Disjunction is defined in a similar way with the union in place of the intersection.
According to this definition, DP = NP ∧ coNP. The other classes of the Boolean hierarchy can be defined as follows.
The following equalities can be used as alternative definitions of the classes of the Boolean hierarchy:
Alternatively, for every k ≥ 3:

Hardness

Hardness for classes of the Boolean hierarchy can be proved by showing a reduction from a number of instances of an arbitrary NP-complete problem A. In particular, given a sequence of instances of A such that xi ∈ A implies xi-1 ∈ A, a reduction is required that produces an instance y such that y ∈ B if and only if the number of xi ∈ A is odd or even:
Such reductions work for every fixed. If such reductions exist for arbitrary, the problem is hard for PNP.