# 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