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
Battle of Changsha

... of Changsha (1941)[?] - Second Chinese-Japanese War merged into World War II Battle of Changsha (1942)[?] - Second Chinese-Japanese War merged into World War ...