patternMinor
$\mathsf{co\text{-}NP}$ and Cook reductions
Viewed 0 times
mathsfcooktextreductionsand
Problem
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?
Solution
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.)
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.)
Context
StackExchange Computer Science Q#14278, answer score: 8
Revisions (0)
No revisions yet.