Wikipedia

Diferencia entre revisiones de «Transformación polinómica»

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
Sin resumen de edición
Deshecha la edición 16116392 de 209.242.141.25 (disc.)
Línea 1:
adan En [[complejidad computacional|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 <math>L\,</math> y <math>M\,</math> [[lenguaje formal|lenguajes formales]] sobre los [[alfabeto]]s <math>\Sigma\,</math> y <math>\Gamma\,</math>, respectivamente. Una transformación polinómica de <math>L\,</math> en <math>M\,</math> es una [[función (matemáticas)|función]] <math>f : \Sigma^* \rightarrow \Gamma^*\,</math> que puede ser calculada en [[tiempo polinómico]] en el tamaño de la entrada con la siguiente propiedad:
Obtenido de «https://es.wikipedia.org/wiki/Transformación_polinómica»