APX (complexité)
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.
Notes et références
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.