Encyclopedia > Polynomial-time many-one reduction

Article Content

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

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

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[?].

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 TLAs from MAA to PZZ ... PQT[?] PQU[?] PQV[?] PQW[?] PQX[?] PQY[?] PQZ[?] PRA[?] PRB[?] PRC PRD[?] PRE[?] PRF[?] PRG[?] PRH[?] PRI PRJ[?] PRK[?] PRL[?] PRM[?] PRN[?] PRO[?] PRP[?] PRQ[?] ...