patternMinor
Why is the Boolean hierarchy contained in the class $P^{NP}$?
Viewed 0 times
whythebooleanhierarchycontainedclass
Problem
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?
Solution
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".
$$ \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".
Context
StackExchange Computer Science Q#23955, answer score: 3
Revisions (0)
No revisions yet.