Transformación polinómica

En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo.

Formalmente, sean L y M lenguajes formales sobre los alfabetos Σ y Γ, respectivamente, una transformación polinómica de L en M es una función computable:

${\displaystyle f:\Sigma ^{*}\rightarrow \Gamma ^{*}\,}$

que puede ser calculada en tiempo polinómico en función del tamaño de la entrada, y que está definida por:

${\displaystyle w\in L\Leftrightarrow f(w)\in M}$

para todo elemento w de Σ^*.

Cuando esta función f existe, se dice que "L es polinómicamente transformable en M".