# proving that $P\ne NP$ under an assumption

Suppose that $P^{SAT} \not\subseteq coNP$. Prove that $P\ne NP$.

What I did:

Suppose that $P=NP$. Then, $P = coP = NP = coNP$.

We know that $P^P = P$.

Then, by assumption: $P^{NP} = NP = coNP$

Since $SAT$ is $NP$-complete we get: $P^{SAT} = coNP$ in contradiction to the assumption.

So $P\ne NP$.

I've been told that my proof is false, but I don't understand why.

• Perhaps you should ask whoever told you that. – Yuval Filmus Sep 24 '17 at 13:37
• @YuvalFilmus, are you implying the proof is alright? – blueplusgreen Sep 24 '17 at 13:51
• It depends on how pedantic you are. That's why I suggest asking what exactly is wrong. – Yuval Filmus Sep 24 '17 at 13:53
• @YuvalFilmus, of course, I should present things more rigoursly but essentilly I think the proof is true. Could you agree on that? – blueplusgreen Sep 24 '17 at 13:54
• One point which could be improved is that it suffices that SAT is in NP. It doesn't matter that it's also NP-hard. Also, some steps are missing, for example you go from $P^P = P$ to $P^{NP} = NP$ and then to $NP = coNP$. But it's largely a matter of taste. – Yuval Filmus Sep 24 '17 at 13:56

## 1 Answer

Here is a more direct proof. Suppose that $P=NP$. In particular, SAT can be solved in polynomial time. Therefore $P^{SAT} \subseteq P^P = P \subseteq coNP$.