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.

  • $\begingroup$ Yes, this is how many-one reducibility is defined for search problems. (People usually study many-one polynomial-time reductions in this context, though.) $\endgroup$ – Emil Jeřábek Apr 12 '17 at 10:59
  • $\begingroup$ 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). $\endgroup$ – Michigan Apr 12 '17 at 13:41
  • $\begingroup$ The poly time version is called a Levin reduction, I believe. $\endgroup$ – Joshua Grochow Apr 12 '17 at 14:25
  • $\begingroup$ See e.g. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, JCSS 48 (1994), p. 506. $\endgroup$ – Emil Jeřábek Apr 12 '17 at 14:26
  • $\begingroup$ @JoshuaGrochow Is it? This is the first time I hear it. $\endgroup$ – Emil Jeřábek Apr 12 '17 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.