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}$? Apr 5, 2013 at 22:12
• @NieldeBeaudrap No i checked again, everything is correct above. Apr 6, 2013 at 9:13
• Shouldn't this be "Prove if a language $k$ is given ..."? Apr 6, 2013 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}$. Apr 6, 2013 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. Apr 6, 2013 at 10:09