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?

  • 1
    $\begingroup$ Can you solidify your intiuition? Why does it feel wrong? $\endgroup$
    – 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$?

  • $\begingroup$ 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? $\endgroup$
    – orezvani
    Apr 16 '14 at 4:31
  • $\begingroup$ @emab Not at all. Turing reductions are less strict than mapping reductions. $\endgroup$ Apr 16 '14 at 11:30
  • $\begingroup$ @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. $\endgroup$ Apr 18 '14 at 0:21
  • $\begingroup$ @user3273554 This is the definition of Turing reducibility. $\endgroup$ Apr 18 '14 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.