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.

  • 1
    $\begingroup$ Perhaps you should ask whoever told you that. $\endgroup$ – Yuval Filmus Sep 24 '17 at 13:37
  • $\begingroup$ @YuvalFilmus, are you implying the proof is alright? $\endgroup$ – blueplusgreen Sep 24 '17 at 13:51
  • $\begingroup$ It depends on how pedantic you are. That's why I suggest asking what exactly is wrong. $\endgroup$ – Yuval Filmus Sep 24 '17 at 13:53
  • $\begingroup$ @YuvalFilmus, of course, I should present things more rigoursly but essentilly I think the proof is true. Could you agree on that? $\endgroup$ – blueplusgreen Sep 24 '17 at 13:54
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 24 '17 at 13:56

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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