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 problema. Puede utilizarse una reducción suficientemente eficaz de un problema a otro 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 determinado (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 ≤ para indicar el tipo de reducción que se utiliza (m: reducción cartográfica , p: reducción polinomial ).
La estructura matemática generada sobre 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 insolubilidad y clases de complejidad .
Hay dos situaciones principales en las que necesitamos utilizar reducciones:
Un ejemplo muy sencillo de reducción es el de la multiplicación al cuadrado . Supongamos que todo lo que sabemos hacer es sumar, restar, sacar al cuadrado y dividir entre 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 un número al cuadrado. 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 vuelve mucho más difícil si agregamos la restricción de que solo podemos usar la función de elevar al cuadrado una vez y solo al final. En este caso, incluso si se nos permite usar todas las operaciones aritméticas básicas, incluida la multiplicación, en general no existe ninguna reducción, porque para obtener el resultado deseado como un cuadrado primero tenemos que calcular su raíz cuadrada, y este cuadrado La raíz podría ser un número irracional como ese que no se puede construir mediante operaciones aritméticas con números racionales. Sin embargo, yendo en la otra dirección, ciertamente podemos elevar un número al cuadrado 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, en general, más difícil que elevar al cuadrado. Esto corresponde a una reducción de muchos uno .
Una reducción es un preordenamiento , es decir una relación reflexiva y transitiva , sobre P ( N )× P ( N ), donde P ( N ) es el conjunto de potencias de los números naturales .
Como se describe en el ejemplo anterior, existen 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, asumiendo 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 problemas en distintas clases de complejidad. Sin embargo, las mayores restricciones a las reducciones de muchos uno hacen que sea más difícil encontrarlas.
Un problema es completo para una clase de complejidad si todos los problemas de la clase se reducen a ese problema y también están en la clase misma. En este sentido, el problema representa la clase, ya que cualquier solución puede, en combinación con las reducciones, usarse para resolver todos los problemas de la clase.
Sin embargo, para que sean ú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 booleano , a un problema trivial, como determinar si un número es igual a cero, haciendo que la máquina reductora resuelva el problema en tiempo exponencial y genere cero. sólo 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 antiguo problema. Asimismo, 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 de la clase [...] Si la reducción en sí fuera difícil de calcular, una solución fácil para la solución completa problema no necesariamente daría una solución fácil a los problemas que se reducen a él."
Por tanto, la noción adecuada de reducción depende de la clase de complejidad que se estudie. Al estudiar la clase de complejidad NP y clases más difíciles como la jerarquía polinómica , se utilizan reducciones de tiempo polinómico . Cuando se estudian clases dentro de P como NC y NL , se utilizan reducciones de 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 únicamente a funciones computables .
En el caso de 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 tales que instancias de un problema se pueden mapear en instancias del otro, de manera que las soluciones casi óptimas para instancias del último problema se pueden 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 una optimización. algoritmo que produce soluciones casi óptimas para casos del problema A. Las reducciones que preservan la aproximación se utilizan a menudo para probar la dureza de los resultados de la 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 algunos α, 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 del problema de detención para demostrar que un lenguaje es indecidible. Supongamos que H ( M , w ) es el problema de determinar si una determinada máquina de Turing M se detiene (aceptando o rechazando) 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 acepta una máquina de Turing determinada M está vacío (en otras palabras, si M acepta alguna cadena). Demostramos que E es indecidible mediante una reducción de H .
Para obtener una contradicción, supongamos que R es un decisor de E. Usaremos esto para producir un decisor S para H (que sabemos que no existe). Dadas las entradas 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 de otra manera. El decisor S ahora puede evaluar R ( N ) para comprobar 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 , podríamos 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.
