# Prove that if $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$

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 ?

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

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.
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.
• 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}$. – Devid Apr 6 '13 at 10:05
• 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. – Devid Apr 6 '13 at 10:09