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

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.