APX (complexité)
Pour les articles homonymes, voir APX.
En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant[1].
Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions[1]. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial.
Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP.
