Transformación polinómica
De Wikipedia, la enciclopedia libre
En teoría de la complejidad computacional, una Transformación polinomial (también conocida como una reducción de Karp) es una forma de reducir un problema de decisión en otro de forma que cualquier algoritmo que resuelva el primer problema produzca inmediatamente una solución al segundo, por un coste polinómico (cuando el problema transformado es suficientemente complejo, este costo resulta despreciable en el cálculo del costo total del problema).
Específicamente, sean 
y 
lenguajes formales sobre los alfabetos 
y 
, respectivamente. Una transformación polinómica de en es una función 
que puede ser calculada en tiempo polinómico en el tamaño de la entrada con la siguiente propiedad:
Cuando esta función 
existe, se dice también que " es polinómicamente transformable en ". La idea de reducir problemas en otros se utiliza también en la definición de varias clases de complejidad, tales como NP-completo, PSPACE-completo y EXPTIME-completo.
