APX
En la 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 de tiempo polinomial 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 la 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 mayor que 1. En el caso de problemas de minimización, es el puntaje de la solución encontrada dividido por el puntaje 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 existe un algoritmo de 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 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 asume P ≠ NP, ningún problema APX-hard tiene un PTAS. En la práctica, la reducción de un problema a otro para demostrar la completitud de APX se realiza a menudo utilizando otros esquemas de reducción, como las reducciones L , que implican reducciones de PTAS.
Uno de los problemas completos de APX 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 pueden ser satisfechas simultáneamente por una única asignación de valores verdadero/falso a las variables.
PTAS ( esquema de aproximación de tiempo polinomial ) consiste en problemas que se pueden aproximar dentro de cualquier factor constante además de 1 en el tiempo que es polinomial al tamaño de entrada, pero el polinomio depende de dicho factor. Esta clase es un subconjunto de APX.