Polynomial-time many-one reduction

In computational complexity theory a polynomial-time many-one reduction (also known as polynomial transformation or Karp reduction) is a certain way to "reduce" one decision problem to another one in such a way that any algorithm solving the latter immediately yields an algorithm solving the former, with only a modest slow-down.

Specifically, suppose L and M are formal languages over the alphabets Σ and Γ, respectively. A polynomial-time many-one reduction from L to M is a function f : Σ^* → Γ^* which can be computed in polynomial time in the input size and has the property that

<math>

  w\in L \Leftrightarrow f(w)\in M\qquad\mbox{for every } w\in\Sigma^*.

</math>

If such a function f exists, we also say that "L is polynomial-time many-one reducible to M". This notion of reducibility is used in the standard definitions of several complexity classes, for instance NP-complete, PSPACE-complete and EXPTIME-complete.

There are other ways to formalize the intuitive idea of reducibility, for example polynomial-time Turing reductions and logarithmic-space many-one reductions[?].