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.

Notes et références

↑ ^{a et b} (en) La classe APX sur le Complexity Zoo.

v · m

Théorie de la complexité (informatique théorique)

Classes de complexité
(liste)

Classes classiques	L NL P NP NP-complet co-NP co-NP-complet NP-facile PSPACE E EXPTIME NE NEXPTIME EXPSPACE
Classes randomisées et quantiques	RP ZPP BPP EQP BQP QMA IP Protocole Arthur-Merlin PP BPL RL
Autres	P/poly NC APX AC⁰ UP
Classes de fonctions calculables	#-P #-P-complet
Hiérarchies	Hiérarchie polynomiale PH Hiérarchie booléenne
Familles de classes	DTIME NTIME DSPACE NSPACE

Théorèmes et outils

Théorèmes structurels	Théorème de Savitch Théorème d'Immerman-Szelepcsényi Théorème PCP Théorème de Karp-Lipton Théorème de Sipser-Gács-Lautemann Théorème de Toda
Outils et réductions	Théorème d'accélération linéaire Théorème de Cook Réduction polynomiale Kernelisation