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

... condemned an Anabaptist for repeating one of its maxims "that alms should not be given before they did sweat in a man's hand." This was between 1518 and 1521. On ...