Reducción de tiempo polinomial

En la teoría de la complejidad computacional, una reducción de tiempo polinomial es un método para resolver un problema usando 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 es polinomial, entonces el primer problema es reducible en tiempo polinomial al segundo.

Una reducción de 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 para el segundo. Las reducciones de tiempo polinomial se utilizan con frecuencia en la teoría de la complejidad para definir clases de complejidad y problemas completos para esas clases.

Tipos de reducciones

Los tres tipos más comunes de reducción de tiempo polinomial, del más al menos restrictivo, son las reducciones de muchos a uno de tiempo polinomial, las reducciones de tabla de verdad y las reducciones de Turing. Las que se utilizan con mayor frecuencia son las reducciones de muchos a uno y, en algunos casos, la frase "reducción de tiempo polinomial" puede usarse para referirse a una reducción de muchos a uno de tiempo polinomial. Las reducciones más generales son las reducciones de Turing y las más restrictivas son las reducciones de muchos uno con reducciones de tablas de verdad que ocupan el espacio intermedio.

Reducciones de varios

Una reducción de muchas veces en un problema A a un problema B (ambos de los cuales suelen ser necesarios para ser problemas de decisión) es un algoritmo de tiempo polinomio para transformar los insumos al problema A in inputs to problem B, tal que el problema transformado tiene la misma salida que el problema original. Una instancia x del problema A se puede resolver aplicando esta transformación para producir una instancia Sí. del problema B, dar Sí. como la entrada a un algoritmo para el problema B, y devolver su salida. Polynomial-time muchas-uno reducciones también se puede conocer como transformaciones polinómicas o Reducciones de Karp, llamado por Richard Karp. Una reducción de este tipo es denotada por A≤ ≤ mPB{displaystyle Aleq _{m} {P}B} o A≤ ≤ pB{displaystyle Aleq _{p}B}.

Reducciones de tablas de verdad

Una reducción polinomio-tiempo de la verdad-tabla de un problema A a un problema B (ambos problemas de decisión) es un algoritmo de tiempo polinomio para transformar las entradas al problema A en un número fijo de entradas para el problema B, tal que la salida para el problema original se puede expresar como una función de los productos para B. La función que mapea los productos para B en la producción para A debe ser lo mismo para todos los insumos, para que pueda ser expresado por una tabla de verdad. Una reducción de este tipo puede ser denotada por la expresión A≤ ≤ ttPB{displaystyle Aleq _{ttt}{P}B}.

Reducciones de Turing

Una reducción de Turing polinomial de un problema A a un problema B es un algoritmo que resuelve el problema A usando un número polinomio de llamadas a una subrutina para el problema B, y tiempo polinomio fuera de esas llamadas de la subrutina. Las reducciones de Turing polinomio-time también se conocen como Reducción de la cocina, llamado por Stephen Cook. Una reducción de este tipo puede ser denotada por la expresión A≤ ≤ TPB{displaystyle Aleq _{T} {P}B}. Muchas reducciones se pueden considerar como variantes restringidas de las reducciones de Turing donde el número de llamadas hechas 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.

Integridad

Un problema completo para una clase de complejidad C dada y reducción ≤ es un problema P que pertenece a C, tal que todo 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 a uno en tiempo polinomial. Se puede demostrar que un problema que pertenece a NP es NP-completo encontrando una sola reducción polinómica en tiempo de muchos a uno a partir de un NP conocido b>- problema completo. Se han utilizado reducciones de muchos a uno en tiempo polinomial para definir problemas completos para otras clases de complejidad, incluidos los lenguajes completos de PSPACE y los lenguajes completos de EXPTIME.

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 a 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 las dos instancias del problema B con diferentes respuestas. Por lo tanto, para las clases de complejidad dentro de P como L, NL, NC y la propia P, las reducciones de tiempo polinomial no se pueden usar para definir lenguajes completos: si se usaran en de esta forma, todos los problemas no triviales en P estarían completos. En su lugar, se utilizan reducciones más débiles, como reducciones de espacio logarítmico o reducciones NC, para definir clases de problemas completos para estas clases, como los problemas P-completos.

Definir clases de complejidad

Las definiciones de las clases de complejidad NP, PSPACE, y EXPTIME no implican reducciones: las reducciones vienen a su estudio sólo en la definición de idiomas completos para estas clases. Sin embargo, en algunos casos una clase de complejidad puede ser definida por reducciones. Si C es cualquier problema de decisión, entonces uno puede definir una clase de complejidad C que consiste en los idiomas A para la cual A≤ ≤ mPC{displaystyle Aleq _{m} {P}C}. En este caso, C se completará automáticamente C, pero C puede tener otros problemas completos también.

Un ejemplo de esto es la clase de complejidad ∃ ∃ R{displaystyle exists mathbb {R} definido de la teoría existencial de los reales, un problema computacional que se sabe que es NP-hard y en PSPACE, pero no se sabe que estar completo NP, PSPACE, o cualquier idioma en la jerarquía polinomio. ∃ ∃ R{displaystyle exists mathbb {R} es el conjunto de problemas que tienen una reducción polinomio-tiempo muchos-uno a la teoría existencial de los reales; tiene varios otros problemas completos tales como determinar el número de cruce rectilineal de un gráfico no dirigido. Cada problema en ∃ ∃ R{displaystyle exists mathbb {R} hereda la propiedad de PSPACE, y cada uno ∃ ∃ R{displaystyle exists mathbb {R}- El problema completo es NP- Hard.

Del mismo modo, 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 se aplica a todos los problemas de esta clase. Un problema es GI-completo si está completo para esta clase; el problema de isomorfismo de grafos en sí mismo es GI-completo, al igual que varios otros problemas relacionados.