En la teoría de complejidad el APX (una abreviatura de la clase del " approximable") es el sistema de los problemas de la optimización de NP que permiten los algoritmos de la aproximación del Polinómico-tiempo con el cociente de la aproximación limitado por un constante (o los algoritmos de la aproximación del constante-factor del para el cortocircuito). En términos simples, los problemas en esta clase tienen algoritmos eficientes que puedan encontrar una respuesta dentro de un cierto porcentaje fijo de la respuesta óptima. Por ejemplo, hay un algoritmo del polinómico-tiempo que encontrará una solución al problema del embalaje del compartimiento que utiliza a lo más el 5% más que el número posible más pequeño de compartimientos.

Un algoritmo de la aproximación se llama un c - algoritmo de la aproximación para un cierto constante c si puede ser probado que la solución que el algoritmo encuentra es a lo más tiempos del c peores que la solución óptima. Aquí, el c se llama el cociente de la aproximación del . Dependiendo de si el problema es una minimización o un problema de la maximización, esto puede denotar los tiempos del c más grandes o los tiempos del c más pequeños, respectivamente. Por ejemplo, el problema de la cubierta de la cima y el problema de vendedor que viaja con la desigualdad del triángulo cada uno tienen 2 algoritmos simples de la aproximación. En contraste con ése ha probado que el problema de vendedor que viaja con borde-longitudes arbitrarias no se puede aproximar con el cociente de la aproximación limitado por un constante mientras el problema de la Hamiltoniano-trayectoria no se pueda solucionar en tiempo polinómico.

Si hay un algoritmo del polinómico-tiempo para solucionar un problema dentro del cada porcentaje fijado (un algoritmo para cada porcentaje), después el problema se dice para tener un esquema (Ptas de la aproximación del Polinómico-tiempo del ). A menos que el P=NP, él pueda ser demostrado que hay los problemas que están en el APX pero no en las Ptas ; es decir, problemas que se pueden aproximar dentro de factor constante de algún, pero no cada factor del constante de . Un problema reputa el APX - difícilmente si hay una reducción de las Ptas de cada problema en el APX a ese problema, y ser el APX - termina si el problema es el APX - difícilmente y también en el APX . Como consecuencia de &ne de las Ptas ; APX, ningún APX - el problema duro está en las Ptas .

Para decir un problema es el APX - están difícilmente generalmente las malas noticias, porque niegan la existencia de las Ptas de un, que son la clase más útil de algoritmo de la aproximación. Uno del más simple APX - los problemas completos son el problema máximo, una variación del satisfiability del problema boleano del satisfiability. En este problema, tenemos una fórmula boleana en la forma normal conjuntiva, y deseamos saber el número máximo de cláusulas que se puedan satisfacer simultáneamente por una tarea única de valores verdaderos/falsos a las variables. A pesar de la falta las Ptas, sin embargo, la respuesta correcta se pueden todavía estimar dentro del 30%, y algunas variantes simplificadas tienen Ptas.

Ejemplos

1. El
del algoritmo de Christofides

.