# If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B?

If $A \leq_m B$ and $A$ is not mapping reducible to $co\text{-}B$, then $A \leq_T co\text{-}B$.

Is this true?

My intuition is false even if we can find some special case to make it true such as $A=B=co\text{-}A_{TM}$. However, I still can't find a counterexample.

Could anyone give me a little hint?

• Can you solidify your intiuition? Why does it feel wrong?
– Raphael
Apr 15 '14 at 10:13

Hint: If $A \leq_m B$ then there is a computable function $f$ such that $x \in A$ iff $f(x) \in B$ iff it is not the case that $f(x) \in \text{co-}B$. Can you use this to Turing-reduce $A$ to $\text{co-}B$?

• If the function f is computable, so it can be computed by a Turing machine, so, is the Truing reduction more restrict than mapping reduction? Apr 16 '14 at 4:31
• @emab Not at all. Turing reductions are less strict than mapping reductions. Apr 16 '14 at 11:30
• @Yuval Filmus Thanks. Should I construct an oracle Turing machine of $co-B$ to decide $A$? This is the only way I could come up to prove the Turing reducibility. Apr 18 '14 at 0:21
• @user3273554 This is the definition of Turing reducibility. Apr 18 '14 at 2:38