En teoría de la computabilidad y teoría de la complejidad computacional , una reducción es un algoritmo para transformar un problema en otro. Una reducción suficientemente eficiente de un problema a otro puede utilizarse para demostrar que el segundo problema es al menos tan difícil como el primero.
Intuitivamente, el problema A es reducible al problema B , si un algoritmo para resolver el problema B de manera eficiente (si existiera) también pudiera usarse como una subrutina para resolver el problema A de manera eficiente. Cuando esto es cierto, resolver A no puede ser más difícil que resolver B. "Más difícil" significa tener una estimación más alta de los recursos computacionales requeridos en un contexto dado (por ejemplo, mayor complejidad de tiempo , mayor requisito de memoria, necesidad costosa de núcleos de procesador de hardware adicionales para una solución paralela en comparación con una solución de un solo subproceso, etc.). La existencia de una reducción de A a B , se puede escribir en la notación abreviada A ≤ m B , generalmente con un subíndice en el ≤ para indicar el tipo de reducción que se está utilizando (m: reducción de mapeo , p: reducción polinomial ).
La estructura matemática generada en un conjunto de problemas por las reducciones de un tipo particular generalmente forma un preorden , cuyas clases de equivalencia pueden usarse para definir grados de irresolubilidad y clases de complejidad .
Hay dos situaciones principales en las que necesitamos utilizar reducciones:
Un ejemplo muy simple de reducción es el de multiplicar por elevar al cuadrado . Supongamos que todo lo que sabemos hacer es sumar, restar, elevar al cuadrado y dividir por dos. Podemos usar este conocimiento, combinado con la siguiente fórmula, para obtener el producto de dos números cualesquiera:
También tenemos una reducción en la otra dirección; obviamente, si podemos multiplicar dos números, podemos elevar al cuadrado un número. Esto parece implicar que estos dos problemas son igualmente difíciles. Este tipo de reducción corresponde a la reducción de Turing .
Sin embargo, la reducción se hace mucho más difícil si añadimos la restricción de que sólo podemos utilizar la función de elevar al cuadrado una vez, y sólo al final. En este caso, incluso si se nos permite utilizar todas las operaciones aritméticas básicas, incluida la multiplicación, no existe ninguna reducción en general, porque para obtener el resultado deseado como un cuadrado tenemos que calcular primero su raíz cuadrada, y esta raíz cuadrada podría ser un número irracional como ese no puede construirse mediante operaciones aritméticas sobre números racionales. Sin embargo, yendo en la otra dirección, ciertamente podemos elevar al cuadrado un número con una sola multiplicación, sólo al final. Utilizando esta forma limitada de reducción, hemos demostrado el resultado nada sorprendente de que la multiplicación es más difícil en general que elevar al cuadrado. Esto corresponde a la reducción de muchos-uno .
Una reducción es una preordenación , es decir una relación reflexiva y transitiva , sobre P ( N )× P ( N ), donde P ( N ) es el conjunto potencia de los números naturales .
Como se describe en el ejemplo anterior, hay dos tipos principales de reducciones utilizadas en la complejidad computacional: la reducción de muchos-uno y la reducción de Turing . Las reducciones de muchos-uno asignan instancias de un problema a instancias de otro; las reducciones de Turing calculan la solución de un problema, suponiendo que el otro problema es fácil de resolver. La reducción de muchos-uno es un tipo más fuerte de reducción de Turing y es más eficaz para separar los problemas en clases de complejidad distintas. Sin embargo, las mayores restricciones en las reducciones de muchos-uno hacen que sean más difíciles de encontrar.
Un problema está completo para una clase de complejidad si todos los problemas de la clase se reducen a ese problema y, además, está dentro de la clase misma. En este sentido, el problema representa a la clase, ya que cualquier solución a él puede, en combinación con las reducciones, utilizarse para resolver todos los problemas de la clase.
Sin embargo, para ser útiles, las reducciones deben ser fáciles . Por ejemplo, es muy posible reducir un problema NP-completo difícil de resolver, como el problema de satisfacibilidad booleana , a un problema trivial, como determinar si un número es igual a cero, haciendo que la máquina de reducción resuelva el problema en tiempo exponencial y dé cero como salida solo si hay una solución. Sin embargo, esto no logra mucho, porque aunque podemos resolver el nuevo problema, realizar la reducción es tan difícil como resolver el problema anterior. Del mismo modo, una reducción que calcula una función no computable puede reducir un problema indecidible a uno decidible. Como señala Michael Sipser en Introducción a la teoría de la computación : "La reducción debe ser fácil, en relación con la complejidad de los problemas típicos en la clase [...] Si la reducción en sí fuera difícil de calcular, una solución fácil para el problema completo no necesariamente produciría una solución fácil para los problemas que se reducen a él".
Por lo tanto, la noción apropiada de reducción depende de la clase de complejidad que se esté estudiando. Cuando se estudia la clase de complejidad NP y clases más difíciles como la jerarquía polinómica , se utilizan reducciones en tiempo polinomial . Cuando se estudian clases dentro de P como NC y NL , se utilizan reducciones en el espacio logarítmico . Las reducciones también se utilizan en la teoría de la computabilidad para mostrar si los problemas son o no solucionables por máquinas; en este caso, las reducciones se restringen solo a funciones computables .
En el caso de los problemas de optimización (maximización o minimización), a menudo pensamos en términos de reducción que preserva la aproximación . Supongamos que tenemos dos problemas de optimización de modo que las instancias de un problema se puedan mapear sobre instancias del otro, de manera que las soluciones casi óptimas para las instancias del último problema se puedan transformar nuevamente para producir soluciones casi óptimas para el primero. De esta manera, si tenemos un algoritmo de optimización (o algoritmo de aproximación ) que encuentra soluciones casi óptimas (u óptimas) para instancias del problema B, y una reducción eficiente que preserva la aproximación del problema A al problema B, por composición obtenemos un algoritmo de optimización que produce soluciones casi óptimas para instancias del problema A. Las reducciones que preservan la aproximación se utilizan a menudo para demostrar la dureza de los resultados de aproximación : si algún problema de optimización A es difícil de aproximar (bajo algún supuesto de complejidad) dentro de un factor mejor que α para algún α, y hay una reducción que preserva la aproximación β del problema A al problema B, podemos concluir que el problema B es difícil de aproximar dentro del factor α/β.
El siguiente ejemplo muestra cómo utilizar la reducción a partir del problema de la detención para demostrar que un lenguaje es indecidible. Supongamos que H ( M , w ) es el problema de determinar si una máquina de Turing dada M se detiene (aceptando o rechazando) en la cadena de entrada w . Se sabe que este lenguaje es indecidible. Supongamos que E ( M ) es el problema de determinar si el lenguaje que una máquina de Turing dada M acepta está vacío (en otras palabras, si M acepta alguna cadena). Demostramos que E es indecidible mediante una reducción a partir de H .
Para obtener una contradicción, supongamos que R es un decisor para E . Usaremos esto para producir un decisor S para H (que sabemos que no existe). Dada la entrada M y w (una máquina de Turing y alguna cadena de entrada), defina S ( M , w ) con el siguiente comportamiento: S crea una máquina de Turing N que acepta solo si la cadena de entrada a N es w y M se detiene en la entrada w , y no se detiene en caso contrario. El decisor S ahora puede evaluar R ( N ) para verificar si el lenguaje aceptado por N está vacío. Si R acepta N , entonces el lenguaje aceptado por N está vacío, por lo que en particular M no se detiene en la entrada w , por lo que S puede rechazar. Si R rechaza N , entonces el lenguaje aceptado por N no está vacío, por lo que M se detiene en la entrada w , por lo que S puede aceptar. Por lo tanto, si tuviéramos un decisor R para E , seríamos capaces de producir un decisor S para el problema de detención H ( M , w ) para cualquier máquina M y entrada w . Como sabemos que tal S no puede existir, se deduce que el lenguaje E también es indecidible.
