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.

$\endgroup$
7
  • 1
    $\begingroup$ Perhaps you should ask whoever told you that. $\endgroup$ Sep 24, 2017 at 13:37
  • $\begingroup$ @YuvalFilmus, are you implying the proof is alright? $\endgroup$ 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$ 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$ 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$ Sep 24, 2017 at 13:56

1 Answer 1

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

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