Reducción del tiempo polinómico
En la teoría de la complejidad computacional , una reducción de tiempo polinomial es un método para resolver un problema utilizando otro. Uno muestra que si existe una subrutina hipotética que resuelve el segundo problema, entonces el primer problema puede resolverse transformándolo o reduciéndolo a entradas para el segundo problema y llamando a la subrutina una o más veces. Si tanto el tiempo requerido para transformar el primer problema en el segundo como el número de veces que se llama a la subrutina son polinomiales , entonces el primer problema es polinomio-tiempo reducible al segundo. [1]
Una reducción de tiempo polinomial prueba que el primer problema no es más difícil que el segundo, porque siempre que existe un algoritmo eficiente para el segundo problema, también existe uno para el primer problema. Por contraposición , si no existe un algoritmo eficiente para el primer problema, tampoco existe para el segundo. [1] Las reducciones de tiempo polinómico se utilizan con frecuencia en la teoría de la complejidad para definir tanto las clases de complejidad como los problemas completos para esas clases.
Los tres tipos más comunes de la mayoría de transformación polinómica, desde las más a las menos restrictivas, son en tiempo polinomial muchos uno-reducciones , reducciones tabla de verdad , y reducciones de Turing . Las que se utilizan con más frecuencia son las reducciones de muchos uno y, en algunos casos, la frase "reducción de tiempo polinomial" puede utilizarse para referirse a una reducción de tiempo polinómico de muchos uno. [2] Las reducciones más generales son las reducciones de Turing y las más restrictivas son las reducciones de muchos uno con reducciones de tabla de verdad que ocupan el espacio intermedio. [3]
Una reducción de muchos uno en tiempo polinomial de un problema A a un problema B (los cuales generalmente se requieren para ser problemas de decisión ) es un algoritmo de tiempo polinomial para transformar las entradas del problema A en entradas del problema B , de modo que el transformado El problema tiene el mismo resultado que el problema original. Una instancia x del problema A se puede resolver aplicando esta transformación para producir una instancia y del problema B , dando y como entrada a un algoritmo para el problema By devolviendo su salida. Las reducciones muchos-uno en tiempo polinómico también se pueden conocer como transformaciones polinómicas o reducciones de Karp , que llevan el nombre de Richard Karp . Una reducción de este tipo se indica con o . [4] [1]
Una reducción de la tabla de verdad en tiempo polinomial de un problema A a un problema B (ambos problemas de decisión) es un algoritmo de tiempo polinomial para transformar las entradas al problema A en un número fijo de entradas al problema B , de manera que la salida del problema original se puede expresar como una función de las salidas para B . La función que mapea las salidas de B en la salida de A debe ser la misma para todas las entradas, de modo que pueda expresarse mediante una tabla de verdad . Una reducción de este tipo puede denotarse mediante la expresión . [5]
