5
$\begingroup$

Prove if a oracle machine $K$ is given with $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$.


Lets assume that $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{co\text{-}P^k}=\mathsf{co\text{-}NP}$. I am stuck here, I don't know how to prove this. Can someone help?

I know that $\mathsf{P}=\mathsf{co\text{-}P}$ but can I also say $\mathsf{P^k}=\mathsf{co\text{-}P^k}$ or do I have to prove it ?

$\endgroup$
3
  • 2
    $\begingroup$ I don't quite understand. What if $K = \mbox{SAT}$? $\endgroup$
    – Pål GD
    Apr 5, 2013 at 22:12
  • $\begingroup$ @NieldeBeaudrap No i checked again, everything is correct above. $\endgroup$
    – Devid
    Apr 6, 2013 at 9:13
  • $\begingroup$ Shouldn't this be "Prove if a language $k$ is given ..."? $\endgroup$
    – frafl
    Apr 6, 2013 at 19:22

1 Answer 1

5
$\begingroup$

Hint: The proof that $\mathsf{P}=\mathsf{co\text{-}P}$ relativizes. That means that if the machines in question are allowed access to some oracle, then the proof goes through. The reason is that the proof just works even when you add the oracle - go over the proof carefully and convince yourself.

"Can I also say that ... or do I have to prove it?" You should be able to answer this yourself. If you can't, go over the definitions a few more times until you really understand what they mean, and then, at the very least, you can say whether "..." follows directly from something that you saw in class, or whether it does not. In the latter case, you should prove it.

In this specific case, given that you already saw a proof of a similarly looking result $\mathsf{P}=\mathsf{co\text{-}P}$, it should seem reasonable to try and see if that same proof generalizes to give $\mathsf{P}^K = \mathsf{co\text{-}P}^K$. In this case it does; in other cases it might not, and then you have to work harder.

$\endgroup$
2
  • 1
    $\begingroup$ I know from my class that $\mathsf{P}=\mathsf{co\text{-}P}$. Now my Turing Machine is connected to a Oracle. I again just need to revert the accept and reject state and i get that $\mathsf{P^k}=\mathsf{co\text{-}P^k}$. $\endgroup$
    – Devid
    Apr 6, 2013 at 10:05
  • $\begingroup$ Now that i have $\mathsf{co\text{-}P^k}=\mathsf{co\text{-}NP}$ and $\mathsf{P^k}=\mathsf{NP}$ and $\mathsf{P^k}=\mathsf{co\text{-}P^k}$ i get (through Transitivity) that $\mathsf{NP}=\mathsf{co\text{-}NP}$. This is actually the proof. $\endgroup$
    – Devid
    Apr 6, 2013 at 10:09

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.