Problem Detail: The question is whether the following statement is true or false: $A leq_T B implies A leq_m B$ I know that if $A leq_T B$ then there is an oracle which can decide A relative to B. I know that this is not enough to say that there is a computable function from A to B that can satisfy the reduction. I don’t know how to word this in the proper way or if what I’m saying is enough to say that the statement is false. How would I go about showing this? EDIT: This is not a homework problem per se, I’m reviewing for a test. Where $leq_T$ is Turing reducibility, and $leq_m$ is mapping reducibility.
Asked By : trigoman
Answered By : Ran G.
The statement is false. Say B is the Halting problem and $A = overline B$. Then, given oracle to the halting problem we can easily decide its complement. However it is not true that $A le_m B$ since $Bin RE$ and $Ain coRE$ but both are undecidable (i.e., if $A le_m B$ was true, then $B=HP$ is both in $RE$ and $coRE$, that is, $Bin R$ which is a contradiction).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1562
