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$

1 Answer 1

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$
4
  • $\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, 2013 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$ Sep 12, 2013 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, 2013 at 19:10
  • $\begingroup$ also note coNP≠NP implies P≠NP because P is closed under complementation $\endgroup$
    – vzn
    Sep 13, 2013 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.