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 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 que la razón de aproximación es una constante . La razón de aproximación se establece convencionalmente mayor que 1. En el caso de 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 ocurre lo contrario. Para problemas de maximización, donde una solución inferior tiene una puntuación menor,a veces se indica como menos de 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 de tiempo polinómico ( PTAS ) si para cada factor multiplicativo del óptimo peor que 1 hay 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 un PTAS, por lo que la clase de problemas con un PTAS está estrictamente contenida en APX. Uno de esos problemas es el problema del embalaje de 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 hace a menudo utilizando otros esquemas de reducción, como 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 se pueden satisfacer simultáneamente con una sola 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 para el tamaño de entrada, pero el polinomio depende de dicho factor. Esta clase es un subconjunto de APX.