2
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ '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? $\endgroup$ – Bread Winner Jul 30 '17 at 20:27
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 30 '17 at 20:29
  • $\begingroup$ I thought NP machines can only accept if there is a short certificate and rejecting needs to verify all paths? $\endgroup$ – Bread Winner Jul 30 '17 at 20:31
  • $\begingroup$ Fortunately, we are taking about a $P^{NP}$ machine. $\endgroup$ – Yuval Filmus Jul 30 '17 at 20:40

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.