En la teoría de la computabilidad y la teoría de la complejidad computacional , especialmente el estudio de los algoritmos de aproximación , una reducción que preserva la aproximación es un algoritmo para transformar un problema de optimización en otro problema, de modo que la distancia de las soluciones con respecto a la óptima se conserva hasta cierto punto. Las reducciones que preservan la aproximación son un subconjunto de reducciones más generales en la teoría de la complejidad; la diferencia es que las reducciones que preservan la aproximación generalmente hacen afirmaciones sobre problemas de aproximación o problemas de optimización , a diferencia de los problemas de decisión .
Intuitivamente, el problema A es reducible al problema B a través de una reducción que preserva la aproximación si, dada una instancia del problema A y un solucionador (posiblemente aproximado) para el problema B, uno puede convertir la instancia del problema A en una instancia del problema B, aplicar el solucionador para el problema B y recuperar una solución para el problema A que también tenga alguna garantía de aproximación.
A diferencia de las reducciones en problemas de decisión, una reducción que preserva la aproximación debe preservar más que la verdad de las instancias del problema cuando se reduce de un problema a otro. También debe mantener alguna garantía sobre la relación entre el costo de la solución y el costo del óptimo en ambos problemas. Para formalizar:
Sean A y B problemas de optimización.
Sea x una instancia del problema A , con solución óptima . Sea y el costo de una solución para una instancia x del problema A. Esta es también la métrica utilizada para determinar qué solución se considera óptima.
Una reducción que preserva la aproximación es un par de funciones (que a menudo deben ser computables en tiempo polinomial), tales que:
Existen muchos tipos diferentes de reducciones que preservan la aproximación, y todas tienen una garantía diferente (el tercer punto de la definición anterior). Sin embargo, a diferencia de otras reducciones, las reducciones que preservan la aproximación a menudo se superponen en las propiedades que demuestran en los problemas de optimización (por ejemplo, pertenencia a una clase de complejidad o completitud, o inaproximabilidad). Los diferentes tipos de reducciones se utilizan en cambio como técnicas de reducción variables, en el sentido de que se utiliza la reducción aplicable que se adapta más fácilmente al problema.
No todos los tipos de reducciones que preservan la aproximación se pueden utilizar para mostrar la pertenencia a todas las clases de complejidad de aproximabilidad, las más notables de las cuales son PTAS y APX . Una reducción a continuación preserva la pertenencia a una clase de complejidad C si, dado un problema A que se reduce al problema B mediante el esquema de reducción, y B está en C, entonces A también está en C. Algunas reducciones que se muestran a continuación solo preservan la pertenencia a APX o PTAS, pero no a la otra. Debido a esto, se debe hacer una elección cuidadosa al seleccionar una reducción que preserve la aproximación, especialmente con el propósito de demostrar la completitud de un problema dentro de una clase de complejidad.
Crescenzi sugiere que los tres estilos de reducción más ideales, tanto por su facilidad de uso como por su poder de prueba, son la reducción PTAS, la reducción AP y la reducción L. [1] Las descripciones de reducción que siguen son del estudio de Crescenzi sobre reducciones que preservan la aproximación.
La reducción estricta es el tipo más simple de reducción que preserva la aproximación. En una reducción estricta, la razón de aproximación de una solución y' a una instancia x' de un problema B debe ser, como máximo, tan buena como la razón de aproximación de la solución y correspondiente a la instancia x del problema A. En otras palabras:
La reducción estricta es la más directa: si existe una reducción estricta del problema A al problema B, entonces el problema A siempre puede aproximarse a una proporción al menos tan buena como la del problema B. La reducción estricta preserva la membresía tanto en PTAS como en APX.
Existe un concepto similar de reducción S, para el cual , y los óptimos de las dos instancias correspondientes deben tener también el mismo coste. La reducción S es un caso muy especial de reducción estricta, y es aún más restrictiva. En efecto, los dos problemas A y B deben estar en correspondencia casi perfecta entre sí. La existencia de una reducción S implica no sólo la existencia de una reducción estricta, sino también de todas las demás reducciones enumeradas aquí.
Las reducciones L preservan la pertenencia a PTAS así como a APX (pero sólo para problemas de minimización en el caso de este último ). Como resultado, no se pueden usar en general para probar resultados de completitud sobre APX, Log-APX o Poly-APX, pero sin embargo son valiosas por su formulación natural y facilidad de uso en pruebas. [1]
La reducción PTAS es otro esquema de reducción que se utiliza con frecuencia. Aunque preserva la pertenencia a PTAS, no lo hace para APX. No obstante, la completitud de APX se define en términos de reducciones PTAS.
Las reducciones PTAS son una generalización de las reducciones P, que se muestran a continuación, con la única diferencia de que se permite que la función g dependa de la relación de aproximación r .
La reducción A y la reducción P son esquemas de reducción similares que se pueden utilizar para mostrar la pertenencia a APX y PTAS respectivamente. Ambos introducen una nueva función c , definida en números mayores que 1, que debe ser computable.
En una reducción A, tenemos que
En una P-reducción, tenemos que
La existencia de una P-reducción implica la existencia de una PTAS-reducción.
La e-reducción, que es una generalización de la reducción estricta pero implica tanto la A-reducción como la P-reducción, es un ejemplo de un estilo de reducción menos restrictivo que preserva la pertenencia no solo en PTAS y APX, sino también en las clases más grandes Log-APX y Poly-APX . La e-reducción introduce dos nuevos parámetros, un polinomio p y una constante . Su definición es la siguiente.
En una E-reducción, tenemos que para algún polinomio p y constante ,
Para obtener una A-reducción a partir de una E-reducción, sea , y para obtener una P-reducción a partir de una E-reducción, sea .
Las reducciones AP se utilizan para definir la completitud en las clases Log-APX y Poly-APX . Son un caso especial de reducción PTAS, que cumple con las siguientes restricciones.
En una reducción AP, tenemos que para alguna constante ,
con la generalización adicional de que se permite que la función g dependa de la relación de aproximación r , como en la reducción PTAS.
La reducción AP también es una generalización de la reducción E. En realidad, se debe imponer una restricción adicional para que la reducción AP preserve la pertenencia a Log-APX y Poly-APX, como lo hace la reducción E: para un tamaño de problema fijo, el tiempo de cálculo de f, g no debe aumentar a medida que aumenta la relación de aproximación.
Una reducción de brecha es un tipo de reducción que, si bien es útil para demostrar algunos resultados de inaproximabilidad, no se parece a las otras reducciones que se muestran aquí. Las reducciones de brecha se ocupan de problemas de optimización dentro de un contenedor de problemas de decisión, generados al cambiar el objetivo del problema para distinguir entre la solución óptima y soluciones con algún factor multiplicativo peor que el óptimo.
