Reducción del tiempo polinómico

método para resolver un problema utilizando otro

En la teoría de la complejidad computacional , una reducción de tiempo polinómico 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 polinomial-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 clases de complejidad como problemas completos para esas clases.

Tipos de reducciones

Los tres tipos más comunes de reducción de tiempo polinómico, desde el más al menos restrictivo, son reducciones muchos uno en tiempo polinómico, reducciones de 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 polinómico" 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 Muchos-uno con reducciones de la Tabla de Verdad que ocupan el espacio intermedio. ^[3]

Reducciones de muchos uno

Una reducción de muchos uno en tiempo polinomial de un problema A a un problema B (ambos 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 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 multinomiales de 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 denota por${\displaystyle A\leq _{m}^{P}B}$ o ${\displaystyle A\leq _{p}B}$. ^{[4] [1]}

Reducciones de la tabla de la verdad

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 del problema A en un número fijo de entradas del problema B , de modo 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${\displaystyle A\leq _{tt}^{P}B}$. ^[5]

Reducciones de Turing

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 polinómico fuera de esas llamadas de subrutina. Las reducciones de Turing en tiempo polinómico también se conocen como reducciones de Cook , que llevan el nombre de Stephen Cook . Una reducción de este tipo puede denotarse mediante la expresión${\displaystyle A\leq _{T}^{P}B}$. ^[4] Las reducciones muchos-uno pueden considerarse 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.

Integridad

Un problema completo para una clase de complejidad dado C y la reducción ≤ es un problema P que pertenece a C , de manera que todos los problemas A en C tiene una reducción de A ≤ P . Por ejemplo, un problema es NP -completo si pertenece a NP y todos los problemas en NP tienen reducciones de varios uno en tiempo polinómico. Se puede demostrar que un problema que pertenece a NP es NP -completo encontrando una única reducción de tiempo polinomial-muchos-uno a partir de un problema NP -completo conocido . ^[6]Se han utilizado reducciones de varios uno en tiempo polinómico para definir problemas completos para otras clases de complejidad, incluidos los lenguajes completos PSPACE y los lenguajes completos EXPTIME . ^[7]

Cada problema de decisión en P (la clase de problemas de decisión de 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 polinómico. 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 clases de complejidad dentro de P como L , NL , NC y PEn sí, las reducciones de tiempo polinómico no pueden usarse para definir lenguajes completos: si se usaran de esta manera, todos los problemas no triviales en P serían completos. En cambio, las reducciones más débiles, como las reducciones de espacio logarítmico o las reducciones NC , se utilizan para definir clases de problemas completos para estas clases, como los problemas P -completos . ^[8]

Definición de clases de complejidad

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 mediante reducciones. Si C es un problema de decisión , entonces se puede definir una clase de complejidad C que consta de los lenguajes A para los cuales${\displaystyle A\leq _{m}^{P}C}$. En este caso, C se completará automáticamente para C , pero C también puede tener otros problemas completos.

Un ejemplo de esto es la clase de complejidad. ${\displaystyle \exists \mathbb {R} }$definido a partir de la teoría existencial de los reales , un problema computacional que se sabe que es NP -hard y en PSPACE , pero que no se sabe que sea completo para NP , PSPACE o cualquier lenguaje en la jerarquía polinomial .${\displaystyle \exists \mathbb {R} }$es el conjunto de problemas que tienen una reducción de varios uno en tiempo polinomial a la teoría existencial de los reales; tiene varios otros problemas completos, como determinar el número de cruce rectilíneo de un gráfico no dirigido . Cada problema en${\displaystyle \exists \mathbb {R} }$hereda la propiedad de pertenecer a PSPACE , y cada${\displaystyle \exists \mathbb {R} }$-El 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 todos los problemas de esta clase. Un problema es GI -complete si está completo para esta clase; el problema de isomorfismo gráfico en sí es GI -completo, al igual que varios otros problemas relacionados. ^[10]

Ver también

• Los 21 problemas NP-completos de Karp

Enlaces externos

• MIT OpenCourseWare: 16. Complejidad: P, NP, NP-completitud, Reducciones

Referencias

1. Kleinberg, Jon; Tardos, Éva Tardos (2006). Diseño de algoritmos . Educación Pearson. págs. 452–453. ISBN 978-0-321-37291-8.
2. Wegener, Ingo (2005), Teoría de la complejidad: exploración de los límites de los algoritmos eficientes , Springer, p. 60, ISBN 9783540274773.
3. Mandal, Debasis; Pavan, A .; Venugopalan, Rajeswari (2014). Separación de la integridad de cocción de la integridad de Karp-Levin bajo una hipótesis de dureza en el peor de los casos . 34º Congreso Internacional sobre la Fundación de la Tecnología del Software y la Informática Teórica. ISBN 978-3-939897-77-4.
4. Goldreich, Oded (2008), Complejidad computacional: una perspectiva conceptual , Cambridge University Press, págs. 59-60, ISBN 9781139472746
5. Buss, SR ; Hay, L. (1988), "Sobre la reducibilidad de la tabla de verdad a SAT y la jerarquía de diferencias sobre NP", Proceedings of Third Annual Structure in Complexity Theory Conference , págs. 224-233, CiteSeerX 10.1.1.5.2387 , doi : 10.1109 /SCT.1988.5282 , ISBN  978-0-8186-0866-7.
6. Garey, Michael R .; Johnson, DS (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman.
7. Aho, AV (2011), "Teoría de la complejidad", en Blum, EK; Aho, AV (eds.), Computer Science: The Hardware, Software and Heart of It , págs. 241–267, doi : 10.1007 / 978-1-4614-1168-0_12 , ISBN 978-1-4614-1167-3. Ver en particular la p. 255.
8. Greenlaw, Raymond; Hoover, James; Ruzzo, Walter (1995), Limits To Parallel computation; Teoría P-Completitud , ISBN 978-0-19-508591-4. En particular, para el argumento de que todo problema no trivial en P tiene una reducción de muchos uno en tiempo polinómico a todos los demás problemas no triviales, véase la p. 48.
9. Schaefer, Marcus (2010), "Complejidad de algunos problemas geométricos y topológicos" (PDF) , Dibujo de gráficos, XVII Simposio Internacional, GS 2009, Chicago, IL, EE. UU., Septiembre de 2009, Artículos revisados , Lecture Notes in Computer Science, 5849 , Springer-Verlag, págs. 334–344, doi : 10.1007 / 978-3-642-11805-0_32 , ISBN  978-3-642-11804-3.
10. Köbler, Johannes; Schöning, Uwe ; Torán, Jacobo (1993), El problema del isomorfismo gráfico: su complejidad estructural , Birkhäuser, ISBN 978-0-8176-3680-7, OCLC  246882287.