APX

En la teoría de la complejidad computacional , la clase APX (abreviatura de "approximable") es el conjunto de problemas de optimización NP que permiten algoritmos de aproximación en tiempo polinomial con una razón de aproximación limitada por una constante (o algoritmos de aproximación de factor constante para abreviar). En términos simples, los problemas de esta clase tienen algoritmos eficientes que pueden encontrar una respuesta dentro de algún factor multiplicativo fijo de la respuesta óptima.

Un algoritmo de aproximación se denomina algoritmo de aproximación para el tamaño de entrada si se puede demostrar que la solución que el algoritmo encuentra es como máximo un factor multiplicativo de veces peor que la solución óptima. Aquí, se llama razón de aproximación . Los problemas en APX son aquellos con algoritmos para los cuales la razón de aproximación es una constante . La razón de aproximación se establece convencionalmente como mayor que 1. En el caso de los problemas de minimización, es la puntuación de la solución encontrada dividida por la puntuación de la solución óptima, mientras que para los problemas de maximización es el caso inverso. Para los problemas de maximización, donde una solución inferior tiene una puntuación menor, a veces se establece como menor que 1; en tales casos, el recíproco de es la relación entre la puntuación de la solución encontrada y la puntuación de la solución óptima.${\displaystyle f(n)}$${\estilo de visualización n}$${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle f(n)}$${\estilo de visualización c}$${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle f(n)}$

Se dice que un problema tiene un esquema de aproximación en tiempo polinomial ( PTAS ) si para cada factor multiplicativo del óptimo peor que 1 existe un algoritmo en tiempo polinomial para resolver el problema dentro de ese factor. A menos que P = NP, existen problemas que están en APX pero sin un PTAS, por lo que la clase de problemas con un PTAS está estrictamente contenida en APX. Un ejemplo de un problema con un PTAS es el problema de empaquetamiento de contenedores .

Se dice que un problema es APX-completo si existe una reducción PTAS de cada problema en APX a ese problema, y ​​que es APX-completo si el problema es APX-completo y también en APX. Como consecuencia de P ≠ NP ⇒ PTAS ≠ APX, si se supone P ≠ NP, ningún problema APX-completo tiene una PTAS. En la práctica, la reducción de un problema a otro para demostrar la completitud APX se realiza a menudo utilizando otros esquemas de reducción, como las reducciones L , que implican reducciones PTAS.

Uno de los problemas APX-completos más simples es MAX-3SAT-3 , una variación del problema de satisfacibilidad booleano . En este problema, tenemos una fórmula booleana en forma normal conjuntiva donde cada variable aparece como máximo 3 veces y deseamos saber el número máximo de cláusulas que se pueden satisfacer simultáneamente mediante una única asignación de valores verdaderos/falsos a las variables.

Otros problemas APX-completos incluyen:

• Conjunto máximo independiente en gráficos de grado acotado (aquí, la relación de aproximación depende del grado máximo del gráfico, pero es constante si el grado máximo es fijo).
• Cobertura mínima de vértices . El complemento de cualquier conjunto independiente máximo debe ser una cobertura de vértices.
• Conjunto mínimo dominante en grafos de grado acotado.
• El problema del viajante de comercio cuando las distancias en el gráfico satisfacen las condiciones de una métrica . TSP es NPO-completo en el caso general.
• El problema de reconfiguración de tokens , a través de la reducción L desde la cubierta del conjunto.

PTAS ( esquema de aproximación de tiempo polinomial ) consiste en problemas que pueden aproximarse a cualquier factor constante distinto de 1 en el tiempo que sea polinomial respecto del tamaño de entrada, pero el polinomio depende de dicho factor. Esta clase es un subconjunto de APX.

A menos que P = NP , existen problemas en APX que no están en PTAS ni APX-completos. Se puede pensar que estos problemas tienen una dificultad entre los problemas PTAS y los problemas APX-completos, y pueden llamarse APX-intermedios . Se piensa que el problema de empaquetamiento de bins es APX-intermedio. A pesar de no tener un PTAS conocido, el problema de empaquetamiento de bins tiene varios algoritmos "PTAS asintóticos", que se comportan como un PTAS cuando la solución óptima es grande, por lo que intuitivamente puede ser más fácil que los problemas que son APX-difíciles.

Otro ejemplo de un problema potencialmente intermedio en APX es la coloración mínima de los bordes .

También se puede definir una familia de clases de complejidad -APX, donde -APX contiene problemas con un algoritmo de aproximación de tiempo polinomial con una razón de aproximación. Se pueden definir análogamente clases -APX-completas; algunas de estas clases contienen problemas de optimización bien conocidos. La completitud log-APX y la completitud poli-APX se definen en términos de reducciones AP en lugar de reducciones PTAS; esto se debe a que las reducciones PTAS no son lo suficientemente fuertes como para preservar la pertenencia en Log-APX y Poly-APX, aunque son suficientes para APX.${\displaystyle f(n)}$${\displaystyle f(n)}$${\displaystyle O(f(n))}$${\displaystyle f(n)}$

Log-APX-completo, que consiste en los problemas más difíciles que pueden aproximarse eficientemente dentro de un factor logarítmico en el tamaño de entrada, incluye el conjunto dominante mínimo cuando el grado es ilimitado.

Poli-APX-completo, que consiste en los problemas más difíciles que pueden aproximarse eficientemente dentro de un polinomio factorial en el tamaño de entrada, incluye el conjunto independiente máximo en el caso general.

También existen problemas que son exp-APX-completos, donde la razón de aproximación es exponencial en el tamaño de entrada. Esto puede ocurrir cuando la aproximación depende del valor de los números dentro de la instancia del problema; estos números pueden expresarse en el espacio logarítmico en su valor, de ahí el factor exponencial.

• Reducción que preserva la aproximación
• Clase de complejidad
• Algoritmo de aproximación
• Teoremas de clasificación de CSP/Unos de máximo/mínimo : un conjunto de teoremas que permiten la clasificación mecánica de problemas sobre relaciones booleanas en clases de complejidad de aproximación
• MaxSNP : una subclase estrechamente relacionada

• Zoológico de la complejidad : APX
• C. Papadimitriou y M. Yannakakis. Optimización, aproximación y clases de complejidad. Journal of Computer and System Sciences, 43:425–440, 1991.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski y Gerhard Woeginger . Maximum Satisfiability Archivado el 13 de abril de 2007 en Wayback Machine . Un compendio de problemas de optimización NP Archivado el 5 de abril de 2007 en Wayback Machine .