2
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Every level of the Boolean hierarchy contains P. $\endgroup$ Nov 1, 2021 at 18:16
  • $\begingroup$ 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. $\endgroup$
    – J.Doe
    Nov 1, 2021 at 18:20
  • $\begingroup$ 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). $\endgroup$ Nov 1, 2021 at 18:21
  • $\begingroup$ 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? $\endgroup$
    – J.Doe
    Nov 1, 2021 at 18:23
  • $\begingroup$ The word require usually has a different connotation in English. $\endgroup$ Nov 1, 2021 at 18:25

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you. I understood why the word 'required' was incorrect. Hats off and a ton of thanks for this insight. It should have been "at most i queries' or 'i queries in the worst case'. thanks again! $\endgroup$
    – J.Doe
    Nov 1, 2021 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.