# Does P^NP=NP imply NP=coNP? [closed]

If you have it, the proof would be appreciated.

Note: P^NP means P with NP oracle

## closed as off-topic by Marzio De Biasi, Jan Johannsen, Aryeh, Emil Jeřábek, GamowFeb 8 at 11:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Marzio De Biasi, Jan Johannsen, Aryeh, Emil Jeřábek, Gamow
If this question can be reworded to fit the rules in the help center, please edit the question.

• 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. – cody Feb 8 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.