HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaModerate

Why does many to one reduction imply Turing reducibility?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
implywhyreducibilityonereductiondoesmanyturing

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#63031, answer score: 17

Revisions (0)

No revisions yet.