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
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.