Intuitive understanding of the Boolean Hierarchy

Question

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<i)$ 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?

Answer 1

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.