patternMinor
An elementary oracle query
Viewed 0 times
oraclequeryelementary
Problem
Why is $P^{NP}\not\subseteq NP$ possible? After all we have a $P$ machine which uses an $NP$ oracle and since $P\subseteq NP$ why cannot the $P$ machine with $NP$ oracle just be replaced by an $NP$ machine?
Similarly why is not the case $P^{coNP}\subseteq coNP$?
Similarly why is not the case $P^{coNP}\subseteq coNP$?
Solution
A $\mathsf{P^{NP}}$ machine can solve $\mathsf{coNP}$ problems: it can query an $\mathsf{NP}$ oracle, and then return the opposite answer. This is not something that you can obviously simulate with an $\mathsf{NP}$ machine.
More concretely, you can construct $\mathsf{P^{NP}}$ machine which gets a formula as input, accepts if the formula is unsatisfiable, and rejects if the formula is satisfiable. How would you implement this as an $\mathsf{NP}$ machine? We only know how to construct witnesses for satisfiability (namely: a truth assignment), but not for unsatisfiability.
More concretely, you can construct $\mathsf{P^{NP}}$ machine which gets a formula as input, accepts if the formula is unsatisfiable, and rejects if the formula is satisfiable. How would you implement this as an $\mathsf{NP}$ machine? We only know how to construct witnesses for satisfiability (namely: a truth assignment), but not for unsatisfiability.
Context
StackExchange Computer Science Q#79394, answer score: 7
Revisions (0)
No revisions yet.