En la teoría de la complejidad computacional , una reducción en tiempo polinomial es un método para resolver un problema utilizando otro. Se muestra que si existe una subrutina hipotética que resuelve el segundo problema, entonces el primer problema se puede resolver 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 reducible en tiempo polinomial al segundo. [1]
Una reducción en tiempo polinomial demuestra 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 primero. Por contraposición , si no existe un algoritmo eficiente para el primer problema, tampoco existe ninguno para el segundo. [1] Las reducciones en tiempo polinomial se utilizan con frecuencia en la teoría de la complejidad para definir tanto clases de complejidad como problemas completos para esas clases.
Los tres tipos más comunes de reducción en tiempo polinómico, desde el más restrictivo hasta el menos restrictivo, son las reducciones de muchos-uno en tiempo polinómico , las reducciones de tabla de verdad y las reducciones de Turing . Las más utilizadas de estas son las reducciones de muchos-uno, y en algunos casos la frase "reducción en tiempo polinómico" puede usarse para referirse a una reducción de muchos-uno en tiempo polinómico. [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 ocupando el espacio intermedio. [3]
Una reducción de muchos-uno en tiempo polinomial de un problema A a un problema B (los cuales normalmente se requieren que sean 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 problema transformado tenga la misma salida 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 B y devolviendo su salida. Las reducciones de muchos-uno en tiempo polinomial también pueden conocerse como transformaciones polinomiales o reducciones de Karp , llamadas así por Richard Karp . Una reducción de este tipo se denota por o . [4] [1]
Una reducción de 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 del problema A en un número fijo de entradas del problema B , de modo que la salida del problema original se pueda expresar como una función de las salidas de B. La función que asigna las salidas de B a la salida de A debe ser la misma para todas las entradas, de modo que se pueda expresar mediante una tabla de verdad . Una reducción de este tipo se puede denotar mediante la expresión . [5]
Una reducción de Turing en tiempo polinomial de un problema A a un problema B es un algoritmo que resuelve el problema A utilizando un número polinomial de llamadas a una subrutina para el problema B y un tiempo polinomial fuera de esas llamadas a la subrutina. Las reducciones de Turing en tiempo polinomial también se conocen como reducciones de Cook , llamadas así por Stephen Cook . Una reducción de este tipo puede denotarse por la expresión . [4] Las reducciones de muchos-uno pueden considerarse como variantes restringidas de las reducciones de Turing donde el número de llamadas realizadas a la subrutina para el problema B es exactamente uno y el valor devuelto por la reducción es el mismo valor que el devuelto por la subrutina.
Un problema completo para una clase de complejidad dada C y reducción ≤ es un problema P que pertenece a C , de modo que cada problema A en C tiene una reducción A ≤ P . Por ejemplo, un problema es NP -completo si pertenece a NP y todos los problemas en NP tienen reducciones de muchos-uno en tiempo polinomial para él. Se puede demostrar que un problema que pertenece a NP es NP -completo al encontrar una única reducción de muchos-uno en tiempo polinomial para él a partir de un problema NP -completo conocido . [6] Las reducciones de muchos-uno en tiempo polinomial se han utilizado para definir problemas completos para otras clases de complejidad, incluidos los lenguajes PSPACE -completos y los lenguajes EXPTIME -completos . [7]
Cada problema de decisión en P (la clase de problemas de decisión en tiempo polinomial) puede reducirse a cualquier otro problema de decisión no trivial (donde no trivial significa que no todas las entradas tienen la misma salida), mediante una reducción de muchos-uno en tiempo polinomial. Para transformar una instancia del problema A en B , resuelva A en tiempo polinomial y luego use la solución para elegir una de dos instancias del problema B con diferentes respuestas. Por lo tanto, para las clases de complejidad dentro de P como L , NL , NC y P mismo, las reducciones en tiempo polinomial no se pueden usar para definir lenguajes completos: si se usaran de esta manera, cada problema no trivial en P sería completo. En cambio, se usan reducciones más débiles como las reducciones en el espacio logarítmico o las reducciones NC para definir clases de problemas completos para estas clases, como los problemas P -completos . [8]
Las definiciones de las clases de complejidad NP , PSPACE y EXPTIME no implican reducciones: las reducciones entran en su estudio solo en la definición de lenguajes completos para estas clases. Sin embargo, en algunos casos una clase de complejidad puede definirse por reducciones. Si C es cualquier problema de decisión , entonces se puede definir una clase de complejidad C que consista en los lenguajes A para los cuales . En este caso, C será automáticamente completa para C , pero C puede tener también otros problemas completos.
Un ejemplo de esto es la clase de complejidad definida a partir de la teoría existencial de los reales , un problema computacional que se sabe que es NP -duro y en PSPACE , pero no se sabe que sea completo para NP , PSPACE o cualquier lenguaje en la jerarquía polinómica . es el conjunto de problemas que tienen una reducción de muchos-uno en tiempo polinomial a la teoría existencial de los reales; tiene varios otros problemas completos como determinar el número de cruces rectilíneos de un grafo no dirigido . Cada problema en hereda la propiedad de pertenecer a PSPACE , y cada problema -completo es NP -duro. [9]
De manera similar, la clase de complejidad GI consta de los problemas que se pueden reducir al problema de isomorfismo de grafos . Dado que se sabe que el isomorfismo de grafos pertenece tanto a NP como a co- AM , lo mismo es cierto para cada problema en esta clase. Un problema es GI -completo si es completo para esta clase; el problema de isomorfismo de grafos en sí mismo es GI -completo, al igual que varios otros problemas relacionados. [10]
