If you have it, the proof would be appreciated.

Note: P^NP means P with NP oracle

  • 1
    $\begingroup$ This is an elementary result, which fits into the more general context of the polynomial hierarchy: en.wikipedia.org/wiki/Polynomial_hierarchy. I'd recommend asking follow up questions on cs.stackexchange.com if you have any. $\endgroup$ – cody Feb 8 '19 at 4:26

Yes, it implies. $P^{NP}$ is the set of languages that are Turing reducible to $NP$ (for example, to $SAT$, or any other $NP$-complete problem). If we take a Boolean formula $F$, then $F\in UNSAT$ holds (meaning that $F$ is not satisfiable), if and only if $\overline{F}$ (the negation of $F$) is satisfiable. Since $UNSAT$ is co-$NP$-complete, and the reduction $F\mapsto\overline F$ is a Turing reduction, therefore, we get $UNSAT\in P^{NP}$, implying co-$NP\subseteq P^{NP}$. If, by assumption, $P^{NP}=NP$, then we get co-$NP\subseteq NP$, which already implies co-$NP= NP$.

I think, a reason for defining $NP$ via polynomial time many-one reductions, rather than Turing reductions is exactly that the latter would not allow the $NP$ vs co-$NP$ distinction.

  • $\begingroup$ Please do not answer off-topic questions. $\endgroup$ – Emil Jeřábek Feb 8 '19 at 10:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.