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 problema. Se puede usar una reducción suficientemente eficiente de un problema a otro para mostrar 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 podría 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 (p. ej., 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 subproceso único, 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 de mapeo , p : reducción polinomial ).
La estructura matemática generada sobre un conjunto de problemas por las reducciones de un determinado tipo generalmente forma un preorden , cuyas clases de equivalencia pueden utilizarse para definir grados de insolubilidad y clases de complejidad .
Un ejemplo muy simple de una reducción es de la multiplicación al cuadrado . Supongamos que todo lo que sabemos hacer es sumar, restar, sacar cuadrados 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 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 este cuadrado raíz podría ser un número irracional como el que no se puede construir mediante operaciones aritméticas en números racionales. Sin embargo, yendo en la otra dirección, ciertamente podemos elevar al cuadrado un número con solo una multiplicación, solo al final. Usando esta forma limitada de reducción, hemos mostrado el resultado poco sorprendente de que la multiplicación es más difícil en general que elevar al cuadrado. esto corresponde areducción de muchos a uno .
