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

<p>I think, a reason for defining <span class="math-container">$NP$</span> via polynomial time many-one reductions, rather than Turing reductions is exactly that the latter would not allow the <span class="math-container">$NP$</span> vs co-<span class="math-container">$NP$</span> distinction.</p>

CC BY-SA 4.0
2019-02-08T10:24:59.823Z
Please do not answer off-topic questions.
Emil Jeřábek
CC BY-SA 4.0
2019-02-08T04:34:43.190Z
2019-02-08T04:34:43.190Z
Andras Farago
<p>If you have it, the proof would be appreciated.</p>

<p>Note: P^NP means P with NP oracle</p>

CC BY-SA 4.0
2019-02-08T04:26:17.173Z
This is an elementary result, which fits into the more general context of the polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy. I'd recommend asking follow up questions on cs.stackexchange.com if you have any.
cody
<cc.complexity-theory><p-vs-np><polynomial-hierarchy>
Does P^NP=NP imply NP=coNP?
Raoul Morin
# Does P^NP=NP imply NP=coNP?

(Asked by: username_0 on 2019-02-08)

If you have it, the proof would be appreciated.

Note: P^NP means P with NP oracle

**Tags:** cc.complexity-theory, p-vs-np, polynomial-hierarchy
> **Comments:**
> **username_1**: This is an elementary result, which fits into the more general context of the polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy. I'd recommend asking follow up questions on cs.stackexchange.com if you have any.  

---

## 1 answers

### Answer by username_2 on 2019-02-08. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_3**: Please do not answer off-topic questions.  

---

