The following definitions are from Li, M., & Vitnyi, P. (1997). An introduction to Kolmogorov complexity and its applications (2nd ed.), pg. 38.A language $A$ is called polynomial time Turing-reducible to a language $B$, denoted as $A\leq_T^P B$, if given $B$ as an oracle, there is a deterministic Turing machine that accepts $A$ in polynomial time. That is, we can accept $A$ in polynomial time given answers to membership of $B$ for free.A language $A$ is called polynomial time many-to-one reducible to a language $B$, denoted as $A\leq_m^P B$, if there is a function $r$ that is a polynomial time computable, and for every $a$, $a\in A$ iff $r(a)\in B$. In both cases, if $B\in P$, then so is $A$.Aren't the two definitions equivalent? What's the difference?
What's the difference between polynomial time Turing-reducible and polynomial time many-to-one reducible?
complexity theory;time complexity;polynomial time