An elementary oracle query

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$?

1 Answer

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 $P^{NP}$ machine which gets a formula as input, accepts if the formula is unsatisfiable' this construction is unclear to me. Could you give details? – Bread Winner Jul 30 '17 at 20:27
• The machine runs the NP oracle on the input formula, and gets from the oracle whether it is satisfiable or not. Then it acts accordingly. – Yuval Filmus Jul 30 '17 at 20:29
• I thought NP machines can only accept if there is a short certificate and rejecting needs to verify all paths? – Bread Winner Jul 30 '17 at 20:31
• Fortunately, we are taking about a $P^{NP}$ machine. – Yuval Filmus Jul 30 '17 at 20:40