Transformación polinómica

Transformación polinómica

En complejidad computacional, una transformación polinomial, reducción polinomial 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 coste polinomial, 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

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.


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Transformación (desambiguación) — Saltar a navegación, búsqueda El término transformación, algunas veces expresado como transformada, puede hacer referencia a los siguientes elementos: En matemáticas Transformada de Fourier, Transformada de Fourier discreta y Transformada rápida… …   Wikipedia Español

  • Transformación — El término transformación hace referencia a la acción o procedimiento mediante el cual algo se modifica, altera o cambia de forma manteniendo su identidad. Adjetivo: transformada, transformado En ciencias sociales Transformación social (redirige… …   Wikipedia Español

  • Teorema de Cook — En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: El Problema de satisfacibilidad booleana (SAT) es NP completo. Stephen Cook (1971) Cook demostró este teorema en su artículo de 1971 The Complexity of Theorem… …   Wikipedia Español

  • NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

  • Co-NP-completo — En teoría de la complejidad computacional, la clase de complejidad co NP completo es el conjunto de los problemas de decisión más difíciles de la clase co NP, en el sentido que son los que menos parecen pertenecer a la clase de complejidad P. De… …   Wikipedia Español

  • LFSR — significa linear feedback shift register, que se traduce como: registro de desplazamiento con retroalimentación lineal. Es un registro de desplazamiento en el cual la entrada es un bit proveniente de aplicar una función de transformación lineal a …   Wikipedia Español

  • Historia de la geometría — La geometría es una de las más antiguas ciencias. Inicialmente, constituía un cuerpo de conocimientos prácticos en relación con las longitudes, áreas y volúmenes. En el Antiguo Egipto estaba muy desarrollada, según los textos de Heródoto,… …   Wikipedia Español

  • Emmy Noether — Amalie Emmy Noether Nacimiento 23 de marzo de 1882 Erlangen, Baviera, Alemania Fallecimiento …   Wikipedia Español

  • Función lineal — Se ha sugerido que Transformación lineal de intervalos sea fusionado en este artículo o sección (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. Para la función entre dos espacios vectoriales… …   Wikipedia Español

  • Sistema-mundo — La perspectiva del sistema mundo, también conocida como economía mundo, o teoría, enfoque o acercamiento analítico de los sistemas mundo (expresión original en inglés World systems approach) es un desarrollo de la crítica post marxista que… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”