APX

En la teoría de la complejidad la clase APX (una abreviatura de "approximable") es el juego de problemas de optimización NP que permiten algoritmos de aproximación del tiempo polinomio con la proporción de aproximación saltada por una constante (o algoritmos de aproximación del factor constante para el corto). En términos simples, los problemas en esta clase tienen algoritmos eficientes que pueden encontrar una respuesta dentro de algún porcentaje fijo de la respuesta óptima. Por ejemplo, hay un algoritmo del tiempo polinomio que encontrará una solución del problema de embalaje del recipiente que usa en el más 5% más que el número más pequeño posible de recipientes.

Se llama un algoritmo de aproximación un algoritmo de c-aproximación algún c constante si se puede probar que la solución que el algoritmo encuentra es en la mayor parte de veces c peores que la solución óptima. Aquí, el c se llama la proporción de aproximación. Según si el problema es una minimización o un problema de maximización, esto puede denotar o tiempos c tiempos más grandes o c más pequeños, respectivamente. Por ejemplo, el problema de la tapa del vértice y problema del viajante de comercio con la desigualdad del triángulo cada uno tiene algoritmos de 2 aproximaciones simples. En contraste, se prueba que el problema del viajante de comercio con longitudes del borde arbitrarias no se puede acercar con la proporción de aproximación saltada por una constante mientras el problema del Camino hamiltoniano no se puede solucionar en el tiempo polinomio, que a menos que P = NP.

Si hay un algoritmo del tiempo polinomio para solucionar un problema dentro de cada porcentaje fijo mayor que el cero (un algoritmo para cada porcentaje), entonces se dice que el problema tiene un esquema de aproximación del tiempo polinomio (PTAS). A menos que P=NP, se pueda mostrar que hay problemas que están en APX, pero no en PESETAS; es decir los problemas que se pueden acercar dentro de algún factor constante, pero no cada factor constante. Se dice que un problema es APX-difícil si hay una reducción de PESETAS de cada problema en APX a ese problema, y ser APX-completa si el problema es APX-difícil y también en APX. Ya que una consecuencia de P ≠ NP ⇒ PESETASAPX, P ≠ NP ⇒ ningún problema APX-difícil está en PESETAS.

Decir un problema es APX-difícil es generalmente malas noticias, porque si P ≠ NP, niegan la existencia de unas PESETAS, que es la clase más útil del algoritmo de aproximación. Uno de los problemas APX-completos más simples es el máximo satisfiability problema, una variación del problema satisfiability booleano. En este problema, tenemos una fórmula booleana en la forma normal conjuntiva, y deseamos saber el número máximo de cláusulas que pueden ser satisfechas simultáneamente por una asignación sola de valores verdaderos/falsos a las variables. A pesar de que probablemente no tiene unas PESETAS, sin embargo, la respuesta correcta todavía se puede estimar dentro del 30%, y algunas variantes simplificadas realmente tienen unas PESETAS.

Ejemplos



Buscar