<p>Many-one reducibility, denoted by $\leq_m$, is a binary relation between 2 decision problems which is defined as follows:
$L' \leq_m L$ iff there exists a computable function $f$ (called a reduction) such that $w \in L' \iff f(w) \in L$.</p>

<p>[source: <a href="https://en.wikipedia.org/wiki/Many-one_reduction]" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Many-one_reduction]</a></p>

<p>Conceptually, if $L'$ is reducible to $L$, we can use an algorithm solving $L$ to solve $L'$ (by first reducing it to an instance of L first).</p>

<p>This conceptual notion is not restricted to decision problems.</p>

<p>I was wondering whether there are equivalents/formal definitions of this type of reducibility that apply to more general problem classes (e.g. function, search problems).</p>

<p>I think m-reducibility on function problems can be defined as follows:</p>

<p>Let $f:X \rightarrow Y$ and $f': X' \rightarrow Y'$ be two function problems. We say $f' \leq_m f$ iff there exist computable functions $a: X' \rightarrow X$ (reduction) and $b:X' \times Y \rightarrow Y'$ (interpretation) such that $f'(x') = b(x',f(a(x'))$.</p>

<p>Note that  m-reducibility for decision problems is a special case obtained if we fix $b(x',y) = y'$ (yes is yes and no is no).</p>

<p>I have also extended this definition to search problems. However, I would very much like to re-use/refer to prior art if possible, but thus far I failed to find an existing definition of the concept.</p>

CC BY-SA 3.0
2017-04-12T10:59:59.613Z
Yes, this is how many-one reducibility is defined for search problems. (People usually study many-one *polynomial-time* reductions in this context, though.)
Emil Jeřábek
CC BY-SA 3.0
2017-04-12T13:41:06.790Z
Could you provide any reference to an article/book defining m-reducibility for search problems as such? (I know it is a somewhat unusual context, explaining why such definition is difficult to find).
Michigan
CC BY-SA 3.0
2017-04-12T14:25:29.893Z
The poly time version is called a Levin reduction, I believe.
Joshua Grochow
CC BY-SA 3.0
2017-04-12T14:26:56.283Z
See e.g. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, JCSS 48 (1994), p. 506.
Emil Jeřábek
CC BY-SA 3.0
2017-04-12T14:28:01.173Z
@JoshuaGrochow Is it? This is the first time I hear it.
Emil Jeřábek
CC BY-SA 3.0
2017-04-12T20:22:22.190Z
@Emil: Yes, see, e.g. http://planetmath.org/levinreduction. Although we more often use Karp reductions nowadays because they're a bit simpler to state, I'm fairly certain Levin reduction for relational problems is the kind that Levin originally used in his definition of NP-complete and in the proof of the Cook-Levin theorem (which is also where he introduced the notion). And most reductions we come up with are actually Levin reductions, since they produce a witness from a witness.
Joshua Grochow
CC BY-SA 3.0
2017-04-12T20:46:03.643Z
The definition on planetmath suffers from typos, but it seems to be stronger than many-one reduction of search problems. There should be no function $g$, and no requirement $R_1(x,y)\to R_2(f(x),g(x,y))$. I only encountered it for total problems where this condition is simply omitted, but I suppose for non-total problems it should state that if $\exists y\,R_1(x,y)$, then $\exists z\,R_2(f(x),z)$.
Emil Jeřábek
CC BY-SA 3.0
2017-04-12T20:52:35.460Z
The search problem (actually, a function) “given an integer $N$ in binary, find the number of prime factors of $N$” is trivially many-one reducible to factorization (i.e., “given $N$, find the list of its prime factors”), but I see no reason there should be a Levin reduction.
Emil Jeřábek
<reductions>
Many-one reducibility equivalent for more general computational problems?
Michigan
# Many-one reducibility equivalent for more general computational problems?

(Asked by: username_0 on 2017-04-12)

Many-one reducibility, denoted by $\leq\_m$, is a binary relation between 2 decision problems which is defined as follows:
$L' \leq\_m L$ iff there exists a computable function $f$ (called a reduction) such that $w \in L' \iff f(w) \in L$.

[source: <https://en.wikipedia.org/wiki/Many-one_reduction]>

Conceptually, if $L'$ is reducible to $L$, we can use an algorithm solving $L$ to solve $L'$ (by first reducing it to an instance of L first).

This conceptual notion is not restricted to decision problems.

I was wondering whether there are equivalents/formal definitions of this type of reducibility that apply to more general problem classes (e.g. function, search problems).

I think m-reducibility on function problems can be defined as follows:

Let $f:X \rightarrow Y$ and $f': X' \rightarrow Y'$ be two function problems. We say $f' \leq\_m f$ iff there exist computable functions $a: X' \rightarrow X$ (reduction) and $b:X' \times Y \rightarrow Y'$ (interpretation) such that $f'(x') = b(x',f(a(x'))$.

Note that m-reducibility for decision problems is a special case obtained if we fix $b(x',y) = y'$ (yes is yes and no is no).

I have also extended this definition to search problems. However, I would very much like to re-use/refer to prior art if possible, but thus far I failed to find an existing definition of the concept.

**Tags:** reductions
> **Comments:**
> **username_1**: Yes, this is how many-one reducibility is defined for search problems. (People usually study many-one *polynomial-time* reductions in this context, though.)  
> **username_0**: Could you provide any reference to an article/book defining m-reducibility for search problems as such? (I know it is a somewhat unusual context, explaining why such definition is difficult to find).  
> **username_2**: The poly time version is called a Levin reduction, I believe.  
> **username_1**: See e.g. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, JCSS 48 (1994), p. 506.  
> **username_1**: @JoshuaGrochow Is it? This is the first time I hear it.  
> **username_2**: @Emil: Yes, see, e.g. http://planetmath.org/levinreduction. Although we more often use Karp reductions nowadays because they're a bit simpler to state, I'm fairly certain Levin reduction for relational problems is the kind that Levin originally used in his definition of NP-complete and in the proof of the Cook-Levin theorem (which is also where he introduced the notion). And most reductions we come up with are actually Levin reductions, since they produce a witness from a witness.  
> **username_1**: The definition on planetmath suffers from typos, but it seems to be stronger than many-one reduction of search problems. There should be no function $g$, and no requirement $R_1(x,y)\to R_2(f(x),g(x,y))$. I only encountered it for total problems where this condition is simply omitted, but I suppose for non-total problems it should state that if $\exists y\,R_1(x,y)$, then $\exists z\,R_2(f(x),z)$.  
> **username_1**: The search problem (actually, a function) “given an integer $N$ in binary, find the number of prime factors of $N$” is trivially many-one reducible to factorization (i.e., “given $N$, find the list of its prime factors”), but I see no reason there should be a Levin reduction.  

---

## 0 answers

