Ir al contenido

Transformación polinómica

De Wikipedia, la enciclopedia libre

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:

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

para todo elemento w de Σ*.

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

Aplicación

[editar]

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.