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

Question

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 ?

Answer 1

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.