HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why is the Boolean hierarchy contained in the class $P^{NP}$?

Submitted by: @import:stackexchange-cs··
0
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".

Context

StackExchange Computer Science Q#23955, answer score: 3

Revisions (0)

No revisions yet.