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.
transformación, polinómica, complejidad, computacional, transformación, polinómica, reducción, polinómica, reducción, karp, manera, relacionar, problemas, decisión, manera, existencia, algoritmo, resuelve, primer, problema, garantiza, inmediatamente, través, t. En complejidad computacional una transformacion polinomica reduccion polinomica o reduccion de Karp es una manera de relacionar dos problemas de decision de manera que la existencia de un algoritmo que resuelve el primer problema garantiza inmediatamente y a traves de un tiempo polinomico la existencia de un algoritmo que resuelve el segundo Formalmente sean L y M lenguajes formales sobre los alfabetos S y G respectivamente una transformacion polinomica de L en M es una funcion computable f S G displaystyle f Sigma rightarrow Gamma que puede ser calculada en tiempo polinomico en funcion del tamano de la entrada y que esta definida por w L f w M displaystyle w in L Leftrightarrow f w in M para todo elemento w de S Cuando esta funcion f existe se dice que L es polinomicamente transformable en M Aplicacion EditarLa idea de reducir problemas en otros se utiliza comunmente en la clasificacion de problemas en varias clases de complejidad tales como NP completo PSPACE completo y EXPTIME completo Datos Q2103034 Obtenido de https es wikipedia org w index php title Transformacion polinomica amp oldid 120646567, wikipedia, wiki, leyendo, leer, libro, biblioteca,
