# $\mathsf{co\text{-}NP}$ and Cook reductions

Can someone help me understand the steps in this argument? There is a decision problem that is in $\mathsf{co\text{-}NP}$ (under standard Karp reductions) and is $\mathsf{NP}$-hard with respect to Cook reductions. Does this imply that if it is in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{co\text{-}NP}$ and if so, why?

## 1 Answer

Every NP-complete program $A$ is co-NP hard under Cook reductions: given a problem $B$ in co-NP, its complement $\overline{B}$ is in NP, so there is a polytime function $f$ such that $f(x) \in A$ iff $x \in \overline{B}$. Therefore the following is a Cook reduction from $B$ to $A$: given $x$, ask whether $f(x) \in A$, and return the opposite.

This shows that Cook reductions are not sensitive to the difference between NP and co-NP. Karp reductions are, and that's why we use them in the usual definition of NP-complete. (If we were only interested in P vs. NP, Cook reductions would be fine.)

• Thank you. To help my confusion, are you saying that if the problem is in NP then it is NP-complete and therefore also co-NP complete and therefore NP=co-NP? What is confusing me is that we normally talk about NP-completeness with respect to Karp reductions I thought. – marshall Sep 12 '13 at 19:04
• If you look at the comments, Yury states that the problem is co-NP-hard with respect to Karp reductions, and so if it is in NP then NP = co-NP. – Yuval Filmus Sep 12 '13 at 19:07
• Ah I see, thank you. Finally the proof that a problem being co-NP-complete and in NP implies that NP=co-NP is at en.wikipedia.org/wiki/Co-NP. – marshall Sep 12 '13 at 19:10
• also note coNP≠NP implies P≠NP because P is closed under complementation – vzn Sep 13 '13 at 17:39