Transformación polinómica
# 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:

    $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:

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

## Aplicación

La idea de reducir problemas en otros se utiliza comúnmente en la clasificación de problemas en varias clases de complejidad, tales como NP-completo, PSPACE-completo y EXPTIME-completo.

* Datos: Q2103034
