Hispanopedia Wiki
Articulo de referencia

Reducción en tiempo polinomial

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 demuestra que si existe una subrutin...

Hispanopedia WikiContenido en espanolLectura gratuita

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 demuestra que si existe una subrutina hipotética que resuelve el segundo problema, entonces el primer problema puede resolverse transformándolo o reduciéndolo a las entradas del 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, ya que si 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. [ 1 ] Las reducciones en tiempo polinomial se utilizan frecuentemente en la teoría de la complejidad para definir tanto clases de complejidad como problemas completos para dichas clases.

Tipos de reducciones

Los tres tipos más comunes de reducción en tiempo polinomial, de más a menos restrictivos, son las reducciones de muchos a uno en tiempo polinomial , las reducciones de tabla de verdad y las reducciones de Turing . Las más utilizadas son las reducciones de muchos a uno, y en algunos casos la expresión "reducción en tiempo polinomial" puede referirse a una reducción de muchos a uno en tiempo polinomial. [ 2 ] Las reducciones más generales son las de Turing y las más restrictivas son las de muchos a uno, con las reducciones de tabla de verdad ocupando un lugar intermedio. [ 3 ]

reducciones de muchos a uno

Una reducción de muchos a uno en tiempo polinomial de un problema A a un problema B (ambos generalmente requeridos como problemas de decisión ) es un algoritmo de tiempo polinomial para transformar las entradas del problema A en entradas del problema B , de manera 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 a uno en tiempo polinomial también se conocen como transformaciones polinomiales o reducciones de Karp , llamadas así en honor a Richard Karp . Una reducción de este tipo se denota porA≤metroPAGB{\displaystyle A\leq _{m}^{P}B}oA≤pagB{\displaystyle A\leq _{p}B}. [ 4 ] [ 1 ]

Reducciones de tablas de verdad

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 en tiempo polinomial para transformar las entradas del problema A en un número fijo de entradas del problema B , de manera que la salida del problema original pueda expresarse como una función de las salidas de B. La función que mapea 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 por la expresiónA≤ttPAGB{\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 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í en honor a Stephen Cook . Una reducción de este tipo puede denotarse mediante la expresiónA≤TPAGB{\displaystyle A\leq _{T}^{P}B}. [ 4 ] Las reducciones de muchos a 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.

Lo completo

Un problema completo para una clase de complejidad C dada y una 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 muchos a uno de tiempo polinomial para él. Se puede demostrar que un problema que pertenece a NP es NP -completo encontrando una única reducción muchos a uno de tiempo polinomial para él a partir de un problema NP -completo conocido. [ 6 ] Las reducciones muchos a uno de 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 a uno en tiempo polinomial. Para transformar una instancia del problema A en B , se resuelve A en tiempo polinomial y luego se utiliza la solución para elegir una de dos instancias del problema B con respuestas diferentes. Por lo tanto, para clases de complejidad dentro de P como L , NL , NC y P misma, las reducciones en tiempo polinomial no pueden utilizarse para definir lenguajes completos: si se utilizaran de esta manera, cada problema no trivial en P sería completo. En cambio, se utilizan reducciones más débiles, como las reducciones en espacio logarítmico o las 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 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 cualquier problema de decisión , entonces se puede definir una clase de complejidad C que consta de los lenguajes A para los cualesA≤metroPAGdo{\displaystyle A\leq _{m}^{P}C}En este caso, C será automáticamente completo para C , pero C también puede tener otros problemas de completitud.

Un ejemplo de esto es la clase de complejidad∃R{\displaystyle \exists \mathbb {R} }definido a partir de la teoría existencial de los reales , un problema computacional que se sabe que es NP -difícil y está en PSPACE , pero no se sabe que sea completo para NP , PSPACE o cualquier lenguaje en la jerarquía polinómica .∃R{\displaystyle \exists \mathbb {R} }es el conjunto de problemas que tienen una reducción de muchos a 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∃R{\displaystyle \exists \mathbb {R} }hereda la propiedad de pertenecer a PSPACE y cada∃R{\displaystyle \exists \mathbb {R} }El problema completo es NP -difícil. [ 9 ]

De manera similar, la clase de complejidad GI consta de los problemas que pueden reducirse al problema del 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 es completo para esta clase; el problema del isomorfismo de grafos en sí mismo es GI -completo, al igual que otros problemas relacionados. [ 10 ]

Véase también

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

Referencias

  1. 1 2 3 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: Explorando los límites de los algoritmos eficientes , Springer, pág. 60, ISBN  9783540274773.
  3. ↑ Mandal, Debasis; Pavan, A.; Venugopalan, Rajeswari (2014). Separando la completitud de Cook de la completitud de Karp-Levin bajo una hipótesis de dificultad en el 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. 1 2 Goldreich, Oded (2008), Complejidad computacional: una perspectiva conceptual , Cambridge University Press, pp. 59–60 , ISBN  9781139472746
  5. ↑ Buss, SR ; Hay, L. (1988), "Sobre la reducibilidad de tablas de verdad a SAT y la jerarquía de diferencias sobre NP", Actas de la Tercera Conferencia Anual sobre Estructura en la Teoría de la Complejidad , pp. 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.), Ciencias de la Computación: El hardware, el software y su esencia , pp. 241–267 , doi : 10.1007/978-1-4614-1168-0_12 , ISBN  978-1-4614-1167-3Véase en particular la página  255.
  8. ↑ Greenlaw, Raymond; Hoover, James; Ruzzo, Walter (1995), Límites de la computación paralela; Teoría de la 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 a uno en tiempo polinomial a cualquier otro problema no trivial, véase la página  48.
  9. ↑ Schaefer, Marcus (2010), "Complejidad de algunos problemas geométricos y topológicos" (PDF) , Graph Drawing, 17.º Simposio Internacional, GS 2009, Chicago, IL, EE. UU., septiembre de 2009, Artículos revisados , Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 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 de grafos: su complejidad estructural , Birkhäuser, ISBN 978-0-8176-3680-7, OCLC 246882287 .