3
$\begingroup$

My textbook says: "The Boolean hierarchy is contained in the class $P^{NP}\subseteq\Sigma^P_2\cap\Pi^P_2$." However, it provides neither a proof nor a proof sketch nor some hint. How can I convince myself that the claim is true?

$\endgroup$
3
$\begingroup$

Every language in the Boolean hierarchy can be written as a "Boolean formula" whose "variables" are languages in NP, e.g. $$ \overline{(L_1 \cap L_2) \cup L_3}. $$ Given an oracle to NP (i.e., an oracle to some NP-complete problem) and an input $x$, we can decide in polytime whether $x \in L_1$, $x \in L_2$, $x \in L_3$. We need polytime since NP-completeness is defined with respect to polynomial time reductions. Given the values of the "variables", it is easy to compute the "formula".

$\endgroup$
  • $\begingroup$ But about half of the "variables" are languages in coNP, aren’t they? $\endgroup$ – user1494080 Apr 21 '14 at 15:06
  • $\begingroup$ If you can decide whether $x \in L$ then you can also decide whether $x \notin L$. $\endgroup$ – Yuval Filmus Apr 21 '14 at 18:17
  • $\begingroup$ That means $coNP\subseteq P^{NP}$, and the inclusion is strict iff $NP\neq coNP$, right? $\endgroup$ – user1494080 Apr 21 '14 at 19:21
  • $\begingroup$ That's correct. $\endgroup$ – Yuval Filmus Apr 21 '14 at 20:24

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.