Problem Detail: So, $ Aleqslant_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} $. $ Aleqslant_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 $.
Asked By : FOKDIEKUL
Answered By : David Richerby
To put it informally, $Aleq_{mathrm{T}}B$ means “If I had a subroutine for $B$, then I could solve $A$”, whereas $Aleq_{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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/63031
