Reducción (complejidad)

En la teoría de la computabilidad y la 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 existe) también puede usarse como 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 temporal , mayor requerimiento de memoria, necesidad de núcleos de procesador adicionales para una solución paralela en comparación con una solución de un solo hilo, etc.). La existencia de una reducción de A a B puede escribirse en la notación abreviada A ≤ _m B , generalmente con un subíndice en ≤ para indicar el tipo de reducción que se está utilizando (m  : reducción de muchos a uno , p  : reducción polinómica ).

La estructura matemática generada en un conjunto de problemas por 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 usar reducciones:

• En primer lugar, nos encontramos intentando resolver un problema similar a uno que ya hemos resuelto. En estos casos, una forma rápida de resolver el nuevo problema suele ser transformar cada instancia del nuevo problema en instancias del problema anterior, resolverlas utilizando nuestra solución existente y, finalmente, usarlas para obtener la solución final. Este es quizás el uso más evidente de las reducciones.
• Segundo: supongamos que tenemos un problema que hemos demostrado que es difícil de resolver, y tenemos un nuevo problema similar. Podríamos sospechar que también es difícil de resolver. Argumentamos por contradicción : supongamos que el nuevo problema es fácil de resolver. Entonces, si podemos demostrar que cada instancia del problema anterior se puede resolver fácilmente transformándola en instancias del nuevo problema y resolviendo estas últimas, tenemos una contradicción. Esto demuestra que el nuevo problema también es difícil.

Un ejemplo muy sencillo de reducción es la que se da entre la multiplicación y la elevación al cuadrado . Supongamos que lo único 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:

${\displaystyle a\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}}$

También tenemos una reducción en la dirección opuesta; 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, no existe reducción en general, porque para obtener el resultado deseado como un cuadrado primero tenemos que calcular su raíz cuadrada , y esta raíz cuadrada podría ser un número irracional como${\displaystyle {\sqrt {2}}}$que no se puede construir mediante operaciones aritméticas sobre números racionales. Sin embargo, en la dirección opuesta, ciertamente podemos elevar al cuadrado un número con una sola multiplicación, solo al final. Usando esta forma limitada de reducción, hemos demostrado el resultado no sorprendente de que la multiplicación es, en general, más difícil que elevar al cuadrado. Esto corresponde a la reducción de muchos a uno .

La reducibilidad es un preordenamiento , es decir, una relación reflexiva y transitiva , en P ( N ) × P ( N ), donde P ( N ) es el conjunto potencia de los números naturales .

Como se describe en el ejemplo anterior, en la teoría de la complejidad computacional se utilizan dos tipos principales de reducciones: la reducción muchos a uno y la reducción de Turing . Las reducciones muchos a 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 es fácil de resolver. La reducción muchos a uno es un tipo más robusto de reducción de Turing y resulta más eficaz para clasificar problemas en distintas clases de complejidad. Sin embargo, las mayores restricciones que imponen las reducciones muchos a uno dificultan su búsqueda.

Un problema se considera completo para una clase de complejidad si todos los problemas de la clase se reducen a ese problema y, además, pertenece a la propia clase. En este sentido, el problema representa la clase, ya que cualquier solución al mismo, en combinación con las reducciones, puede utilizarse para resolver todos los problemas de la clase.

Sin embargo, para que sean útiles, las reducciones deben ser fáciles . Por ejemplo, es perfectamente 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 lo resuelva en tiempo exponencial y genere cero solo si existe una solución. Sin embargo, esto no resulta muy útil, ya que, aunque podamos resolver el nuevo problema, realizar la reducción es igual de difícil que resolver el problema original. 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 de la clase [...] Si la reducción en sí misma fuera difícil de calcular, una solución fácil al problema completo no necesariamente produciría una solución fácil a los problemas que la reducen».

Por lo tanto, la noción apropiada de reducción depende de la clase de complejidad que se esté estudiando. Al estudiar la clase de complejidad NP y muchas clases más difíciles, como la jerarquía polinómica , se utilizan reducciones en tiempo polinomial . Al estudiar clases dentro de P, como NC y NL , se utilizan reducciones en espacio logarítmico . Las reducciones también se utilizan en la teoría de la computabilidad para determinar si los problemas son o no resolubles por máquinas; en este caso, las reducciones se limitan a funciones computables (para reducciones de muchos a uno) o a máquinas oráculo (para reducciones de Turing).

En el caso de problemas de optimización (maximización o minimización), solemos pensar en términos de reducciones que preservan la aproximación . Supongamos que tenemos dos problemas de optimización tales que las instancias de un problema se pueden mapear a instancias del otro, de manera que las soluciones casi óptimas para las instancias del segundo problema se pueden transformar de nuevo para producir soluciones casi óptimas para el primero. De esta forma, 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 dificultad de los resultados de aproximación: si algún problema de optimización A es difícil de aproximar (bajo alguna suposición 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 α / β .

• Para demostrar que un problema de decisión A es indecidible, debemos encontrar una reducción de un problema de decisión que ya se sabe que es indecidible a A. Dicha función de reducción debe ser una función computable . En particular, a menudo demostramos que un problema A es indecidible mostrando que el problema de la parada se reduce a A.
• Las clases de complejidad P , NP y PSPACE son cerradas bajo reducciones de tiempo polinomial (muchos-uno, "Karp") .
• Las clases de complejidad L , NL , P , NP y PSPACE son cerradas bajo la reducción del espacio logarítmico .

• Reducción de grano fino
• Dispositivo (informática)
• reducción de muchos a uno
• Reducción parsimoniosa
• Reducción (teoría de la recursión)
• Reducción de tabla de verdad
• reducción de Turing

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein , Introducción a los algoritmos, MIT Press, 2001, ISBN 978-0-262-03293-3
• Hartley Rogers Jr .: Teoría de las funciones recursivas y la computabilidad efectiva, McGraw-Hill, 1967, ISBN 978-0-262-68052-3.
• Peter Bürgisser : Completitud y reducción en la teoría de la complejidad algebraica, Springer, 2000, ISBN 978-3-540-66752-0.
• ER Griffor: Manual de teoría de la computabilidad, North Holland, 1999, ISBN 978-0-444-89882-1.