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