En teoría de la complejidad computacional , la clase APX (una abreviatura de "aproximable") es el conjunto de problemas de optimización NP que permiten algoritmos de aproximación en tiempo polinómico con una relació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 encuentra el algoritmo es como máximo un factor multiplicativo de veces peor que la solución óptima. Aquí, se llama relación de aproximación . Los problemas en APX son aquellos con algoritmos para los cuales la relación de aproximación es una constante . La relación de aproximación se establece convencionalmente como mayor que 1. En el caso de problemas de minimización, la puntuación de la solución encontrada se divide por la puntuación de la solución óptima, mientras que para los problemas de maximización ocurre lo contrario. Para problemas de maximización, donde una solución inferior tiene una puntuación menor, a veces se indica 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.
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 hay 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 PTAS, por lo que la clase de problemas con PTAS está estrictamente contenida en APX. Uno de esos problemas es el problema del embalaje en los contenedores .
Se dice que un problema es APX-difícil si hay una reducción de PTAS de cada problema en APX a ese problema, y que es APX-completo si el problema es APX-difícil y también en APX. Como consecuencia de P ≠ NP ⇒ PTAS ≠ APX, si se supone P ≠ NP, ningún problema APX-duro tiene un PTAS. En la práctica, la reducción de un problema a otro para demostrar la completitud de APX a menudo se realiza utilizando otros esquemas de reducción, como las reducciones L , que implican reducciones de PTAS.
Uno de los problemas APX-completos más simples es MAX-3SAT-3 , una variación del problema booleano de satisfacibilidad . 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 pueden satisfacerse simultáneamente mediante una única asignación de valores verdadero/falso a las variables.
Otros problemas de APX completo incluyen:
PTAS ( esquema de aproximación de tiempo polinómico ) consta de problemas que se pueden aproximar dentro de cualquier factor constante además de 1 en el tiempo que sea polinomio al 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 completos en PTAS ni en APX. Se puede considerar que estos problemas tienen una dureza entre los problemas PTAS y los problemas APX completos, y pueden denominarse APX intermedio . Se cree que el problema del embalaje del contenedor es de nivel intermedio APX. A pesar de no tener un PTAS conocido, el problema del embalaje de contenedores 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 de APX es la coloración mínima del borde .
También se puede definir una familia de clases de complejidad -APX, donde -APX contiene problemas con un algoritmo de aproximación de tiempo polinómico con una relación de aproximación. De manera análoga se pueden definir 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 de PTAS no son lo suficientemente fuertes como para preservar la membresía en Log-APX y Poly-APX, aunque sean suficientes para APX.
Log-APX-complete, que consta de los problemas más difíciles que se pueden aproximar eficientemente dentro de un factor logarítmico en el tamaño de entrada, incluye un conjunto dominante mínimo cuando el grado es ilimitado.
Poly-APX-complete, que consta de los problemas más difíciles que se pueden aproximar eficientemente dentro de un polinomio factorial en el tamaño de entrada, incluye un conjunto máximo independiente en el caso general.
También existen problemas que son exp-APX-completos, donde la relació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.
