Problem Detail: Can someone help me understand the steps in this argument? There is a decision problem that is in $mathsf{cotext{-}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{cotext{-}NP}$ and if so, why?
Asked By : marshall
Answered By : Yuval Filmus
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.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14278 Ask a Question Download Related Notes/Documents
