# 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

• 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, 2019 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.