2
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Perhaps you should ask whoever told you that. $\endgroup$
    – Yuval Filmus
    Commented Sep 24, 2017 at 13:37
  • $\begingroup$ @YuvalFilmus, are you implying the proof is alright? $\endgroup$
    – blueplusgreen
    Commented Sep 24, 2017 at 13:51
  • $\begingroup$ It depends on how pedantic you are. That's why I suggest asking what exactly is wrong. $\endgroup$
    – Yuval Filmus
    Commented Sep 24, 2017 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
    Commented Sep 24, 2017 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
    Commented Sep 24, 2017 at 13:56

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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