1
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by D.W., Juho, Luke Mathieson, vonbrand, Kaveh Feb 7 '14 at 6:13

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ 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. $\endgroup$ – Raphael Jan 13 '14 at 16:01
1
$\begingroup$

A polynomial-time many-one reduction is a polynomial Turing reduction that only calls the oracle once, and that returns the oracle's answer without any further computation.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.