7
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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 $B\in RE$ and $A\in 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, $B\in R$ which is a contradiction).

$\endgroup$
7
$\begingroup$

It is false: take $Diag = \{\langle M \rangle \mid M \notin L(M) \}$ and its complement.

Generally $\leq_T$ can be used to reduce a problem to its complement while $\leq_m$ cannot.

If you want to know see more kinds of reductions and examples that they are different I suggest having a look at "Classical Recursion Theory" by Odifreddi.

$\endgroup$
2
$\begingroup$

There is a general fact that every noncomputable Turing degree contains infinitely many distinct $m$-degrees.

(This result follows at least from results of Jockusch, "Relationships between reducibilities", Trans. Amer. Math. Soc. 142 (1969), 229-237. It might have been known before that.)

$\endgroup$

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.