# Intuitive understanding of the Boolean Hierarchy

I am trying to understand the Boolean Hierarchy. the formal definition of the Boolean Hierarchy is as follows:

• $$BH_1 = NP$$

• $$BH_{2k}$$ is the class of languages which are the intersection of a language in $$BH_{2k-1}$$ and a language in $$coNP$$.

• $$BH_{2k+1}$$ is the class of languages which are the intersection of a language in $$BH_{2k}$$ and a language in $$NP$$.

• $$BH$$ is the union of the $$BH_i$$

I am clear with the formal definition but not many sources explain it intuitively. Lets decipher it as follows:

• $$BH_1 = NP_0$$
• $$BH_2 = NP_0\cap coNP_1$$
• $$BH_3 = (NP_0\cap coNP_1) \cup (NP_1)$$

Thus if language is in $$BH_3$$ iff: Its first language (namely $$NP_0$$) is satisfiable, second language (namely $$coNP_0$$) is unsatisfiable, and third language (namely $$NP_1$$) is satisfiable.

Alternatively, can we define the complexity levels in $$BH$$ as follows:

$$BH_i$$: A language is in $$BH_i$$ iff it requires $$i$$ oracle calls to an $$NP$$-oracle to solve the problem in polynomial time. Thus, for any $$BH_i$$ there seems to be no algorithm that solves the problem in polynomial time with $$j$$ oracle calls, where $$(j to an $$NP$$-oracle ((in the worst case).

Is this alternate definition equivalent to the formal definition or there is some flaw in the understanding?

• Every level of the Boolean hierarchy contains P. Nov 1, 2021 at 18:16
• The way I understand the first level is $NP$ thus it requires 1 call to $NP$ oracle to solve it in polynomial time and so on. Can we say the classes below ($P$ as you said) are at the 0th level and will require 0 calls to this oracle to solve the problem in polynomial time? Its seems consistent. Nov 1, 2021 at 18:20
• NP contains P. A problem in NP doesn't "require" a single oracle call. It's exactly the opposite: it can be solved using a single oracle call (and in a particular way). Nov 1, 2021 at 18:21
• When I said it requires an oracle call I meant the same i.e. $BH_i$ can be solved in polynomial time with 'i' oracle calls to an NP oracle. am I wrong somewhere? Nov 1, 2021 at 18:23
• The word require usually has a different connotation in English. Nov 1, 2021 at 18:25

The Boolean hierarchy is cumulative: $$\mathrm{BH}_n \subseteq \mathsf{BH}_{n+1}$$. In particular, all levels of the Boolean hierarchy contain $$\mathrm{P}$$.
The introduction to Pitassi, Shirley and Watson's Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity contains some equivalent definitions of the Boolean hierarchy, and relevant pointers to the literature. The simplest definition that they give is: $$\mathrm{BH}_n$$ is the set of decision problems computable by making $$n$$ many $$\mathrm{NP}$$ oracle calls, and outputting the parity of the result.