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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.)
answered Sep 12, 2013 at 18:18
-
$\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$– marshallSep 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$– marshallSep 12, 2013 at 19:10
-
$\begingroup$ also note coNP≠NP implies P≠NP because P is closed under complementation $\endgroup$– vznSep 13, 2013 at 17:39