Boolean hierarchy

The boolean hierarchy is the hierarchy of boolean combinations (intersection, union and complementation) of NP sets.

Disjunction is defined in a similar way with the union in place of the intersection.

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:[4] Alternatively,[5] for every k ≥ 3: 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 {x1, ... xm} 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:[4] Such reductions work for every fixed k. If such reductions exist for arbitrary k, the problem is hard for PNP[O(log n)].