7
$\begingroup$

So, $ A\leqslant_mB $ (many to one reduction) means that language $A$ can be reduced to language $B$ if there exists a Turing-calculable function $f$ so $ f(A) \subseteq B$ and $ f(\overline{A}) \subseteq \overline{B} $.

$ A\leqslant_TB $ (Turing reducibility) means that language $A$ can be Turing-reduced to language $B$ if there exists an oracle machine $O^B$ which decides $A$.

I sort of get them both individually, but I don't get why $ \leqslant_m $ implies $ \leqslant_T $.

$\endgroup$
  • $\begingroup$ Consider $A \leq_m B$. then you have this Turing-computable function $f$ with that property. Now consider a word $w$. We want to decide whether $w \in A$. But then we can just check whether $f(w) \in B$. That's because if $w \in A$ then we know that $f(w) \in B$ and if $w \notin A$ then we know that $f(w) \notin B$ hence the function $f$ basically is the oracle machine $O^B$ that you need to determine $A \leq_T B$. $\endgroup$ – Bakuriu Aug 30 '16 at 18:56
15
$\begingroup$

To put it informally, $A\leq_{\mathrm{T}}B$ means "If I had a subroutine for $B$, then I could solve $A$", whereas $A\leq_{\mathrm{m}}B$ means, "If I had a subroutine for $B$, then I could solve $A$ using a program that calls the subroutine only once and, furthermore, just returns the answer of the subroutine without doing any further calculation."

If you can solve a problem using a subroutine such that blah blah blah, you can solve that problem using the subroutine.

$\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.