4
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – marshall Sep 12 '13 at 19:04
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 12 '13 at 19:07
  • $\begingroup$ 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. $\endgroup$ – marshall Sep 12 '13 at 19:10
  • $\begingroup$ also note coNP≠NP implies P≠NP because P is closed under complementation $\endgroup$ – vzn Sep 13 '13 at 17:39

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.