If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B
-
16-10-2019 - |
Question
I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false.
By the definition of $\leq_m$ we can construct the following statement,
$w \in A \iff f(w) \in B \rightarrow w \notin A \iff f(w) \notin B$
This is where I'm stuck, I want to say that since we have such computable function $f$ then it'll only give us the mapping from A to B if there is one, otherwise it wont.
I don't know how to phrase this correctly, or if I'm even on the right track.
Solution
As Dave said, it follows from a simple logical equivalence: $p \leftrightarrow q$ is the same as $\lnot p \leftrightarrow \lnot q$. Now put $p= w\in A$ and $q = f(w) \in B$.
$A \leq_m B$ means there is a total computable $f$ s.t. for all $w$,
$w \in A \leftrightarrow f(w) \in B$.
By the argument above, this is the same as
$w \notin A \leftrightarrow f(w) \notin B$.
Or equivalently
$w \in \bar{A} \leftrightarrow f(w) \in \bar{B}$.
And therefore, the same $f$ shows that $\bar{A} \leq_m \bar{B}$.
OTHER TIPS
$A \leq_m B$ does not implie $w \in A \leftrightarrow f(w) \in B$ only the other way is true if $w \in A \leftrightarrow f(w) \in B$ then $A \leq_m B$ but not reciprocaly