Reducción del tiempo polinomial

Método para resolver un problema usando otro.

En la teoría de la complejidad computacional , una reducción del 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 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 necesario 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 en tiempo polinómico reducible al segundo. ^[1]

Una reducción del 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 de 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.

Tipos de reducciones

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 muchos uno en tiempo polinómico , las reducciones de tablas de verdad y las reducciones de Turing . Las más utilizadas son las reducciones de muchos uno y, en algunos casos, la frase "reducción de tiempo polinomial" puede usarse para referirse a una reducción de muchos uno en tiempo polinomial. ^[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 tablas de verdad que ocupan el espacio intermedio. ^[3]

Reducciones de muchos uno

Una reducción de muchos en tiempo polinomial de un problema A a un problema B (generalmente se requiere que ambos sean problemas de decisión ) es un algoritmo de tiempo polinómico para transformar entradas al problema A en entradas al problema B , de modo que las transformadas 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 B y devolviendo su salida. Las reducciones muchos-uno en tiempo polinomial también pueden conocerse como transformaciones polinómicas o reducciones de Karp , que llevan el nombre de Richard Karp . Una reducción de este tipo se denota por o . ^{[4] [1]} ${\displaystyle A\leq _{m}^{P}B}$ ${\displaystyle A\leq _{p}B}$

Reducciones de la tabla de 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 al 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 asigna las salidas de B a 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] ${\displaystyle A\leq _{tt}^{P}B}$

Reducciones de Turing

Una reducción de Turing en tiempo polinómico de un problema A a un problema B es un algoritmo que resuelve el problema A utilizando un número polinómico de llamadas a una subrutina para el problema B y tiempo polinómico fuera de esas llamadas a subrutinas. Las reducciones de Turing en tiempo polinomial también se conocen como reducciones de Cook , nombradas así en honor a Stephen Cook . Una reducción de este tipo puede denotarse mediante 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. ${\displaystyle A\leq _{T}^{P}B}$

Lo completo

Un problema completo para una determinada clase de complejidad C y reducción ≤ es un problema P que pertenece a C , de modo 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 uno en tiempo polinomial. Se puede demostrar que un problema que pertenece a NP es NP completo encontrando una única reducción de muchos en tiempo polinomial a partir de un problema NP completo conocido. ^[6] Se han utilizado reducciones de muchos uno en tiempo polinomial 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 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 las dos instancias del problema B con diferentes respuestas. Por lo tanto, para clases de complejidad dentro de P como L , NL , NC y el propio P , las reducciones de tiempo polinomial no pueden usarse para definir lenguajes completos: si se usaran de esta manera, todos los problemas no triviales en P estarían completos. En cambio, 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 . ^[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 sólo 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 cualquiera , entonces se puede definir una clase de complejidad C que consta de los lenguajes A para los cuales . En este caso, C se completará automáticamente para C , pero C también puede tener otros problemas completos. ${\displaystyle A\leq _{m}^{P}C}$

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 -difícil y en PSPACE , pero que no se sabe que esté completo para NP , PSPACE o cualquier lenguaje en el polinomio. jerarquía . 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 cruce rectilíneo de un gráfico no dirigido . Cada problema hereda la propiedad de pertenecer a PSPACE y cada problema completo es NP difícil. ^[9] ${\displaystyle \exists \mathbb {R} }$ ${\displaystyle \exists \mathbb {R} }$ ${\displaystyle \exists \mathbb {R} }$ ${\displaystyle \exists \mathbb {R} }$

De manera similar, la clase de complejidad GI consta de 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 ocurre con todos los problemas de esta clase. Un problema es GI -completo 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 (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 Cook de la integridad de Karp-Levin según la hipótesis de dureza del peor de los casos. 34ª Conferencia Internacional sobre Fundamentos 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. Autobús, SR ; Hay, L. (1988), "Sobre la reducibilidad de la tabla de verdad a SAT y la jerarquía de diferencias sobre NP", Actas de la tercera conferencia anual sobre estructura en teoría de la complejidad , 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), Computadoras e intratabilidad: una guía para la teoría de la integridad NP , WH Freeman.
7. Aho, AV (2011), "Teoría de la complejidad", en Blum, EK; Aho, AV (eds.), Ciencias de la computación: el hardware, el software y el corazón , págs. 241–267, doi : 10.1007/978-1-4614-1168-0_12 , ISBN 978-1-4614-1167-3. Véase en particular la pág. 255.
8. Ley verde, Raymond; Hoover, James; Ruzzo, Walter (1995), Límites del cálculo paralelo; Teoría de la completitud P , 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 polinomial con respecto a todos los demás problemas no triviales, consulte la p. 48.
9. Schaefer, Marcus (2010), "Complejidad de algunos problemas geométricos y topológicos" (PDF) , dibujo gráfico, 17º simposio internacional, GS 2009, Chicago, IL, EE. UU., septiembre de 2009, artículos revisados , notas de conferencias en informática, vol. . 5849, Springer-Verlag, págs. 334–344, doi : 10.1007/978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
10. Kobler, Johannes; Schöning, Uwe ; Torán, Jacobo (1993), El problema del isomorfismo de grafos: su complejidad estructural , Birkhäuser, ISBN 978-0-8176-3680-7, OCLC  246882287.