# What's the difference between “polynomial time Turing-reducible” and “polynomial time many-to-one reducible”? [duplicate]

The following definitions are from Li, M., & Vitányi, 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?

• I think this question has been answered in any of the following questions: 1, 2, 3. Bottom line: The former allows multiple calls to the oracle, which gives you more power in a certain sense. – Raphael Jan 13 '14 at 16:01