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
Wikipedia:Bad jokes and other deleted Nonsense N-Z

... harm a human being, or allow a human being to be harmed. Al Gore must obey the orders given by the human beings, except where such orders would conflict with the First ...