APX (complexité)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]