Transformación polinómica

De Wikipedia, la enciclopedia libre
(Redirigido desde «Reducción polinomial»)
Saltar a: navegación, búsqueda

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