title: Transformación polinómica
text: # 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".
  
  # Transformación polinómica
  ## 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