Liste de classes de complexité

Cet article présente une liste de classes de complexité en théorie de la complexité.

Classe	Description	Relation
#P	compte les solutions d'un problème de NP
#P-complet	#P et tout problème #P peut s'y ramener par réduction polynomiale
2-EXPTIME	décidable en temps doublement exponentiel	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{2^{n^{k}}}\right)}$
AC	réunion des classes de la hiérarchie AC^i	${\displaystyle \bigcup _{i\in \mathbb {N} }{\mbox{AC}}^{i}}$ ; égale à ${\displaystyle {\mbox{NC}}}$
AC^0	calculable par un circuit booléen de profondeur constante, de taille polynomiale
AC^i	calculable par un circuit booléen de profondeur ${\displaystyle O(\log ^{i}n)}$, de taille polynomiale
ALL	tous les problèmes de décision
AM	décidable en temps polynomial par un protocole Arthur-Merlin à deux messages
APX	existence d'un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant
BPP	décidable en temps polynomial par une machine de Turing probabiliste avec une probabilité d'erreur inférieure à 1/3
BQP	décidable en temps polynomial par un calculateur quantique avec une probabilité d'erreur inférieure à 1/3
co-NP	réponse négative vérifiable en temps polynomial
co-NP-complet	co-NP et tout problème co-NP peut s'y ramener par réduction polynomiale
DSPACE(f(n))	décidable par une machine déterministe en espace O(f(n))
DTIME(f(n))	décidable par une machine déterministe en temps O(f(n))
E	décidable en temps exponentiel avec un exposant linéaire	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{kn}\right)}$
ELEMENTARY	réunion des classes de la hiérarchie exponentielle (en)	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{k-EXPTIME}}={\mbox{DTIME}}\left(2^{n}\right)\cup {\mbox{DTIME}}\left(2^{2^{n}}\right)\cup {\mbox{DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots }$
ESPACE	décidable en espace exponentiel avec un exposant linéaire	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}\left(2^{kn}\right)}$
EXPSPACE	décidable en espace exponentiel	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}\left(2^{n^{k}}\right)}$ ; égale à${\displaystyle {\mbox{ NEXPSPACE }}}$par le théorème de Savitch
EXPTIME (ou EXP)	décidable en temps exponentiel	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right)}$
IP	décidable par un système de preuve interactive	égale à${\displaystyle {\mbox{ PSPACE }}}$
L	décidable en espace logarithmique	${\displaystyle {\mbox{DSPACE }}(\log(n))}$
LOGCFL	réductible en espace logarithmique à un langage hors-contexte
NC	décidable en temps polylogarithmique par un nombre polynomial de machines en parallèle	égale à ${\displaystyle {\mbox{AC}}}$
NE	décidable par une machine non déterministe en espace exponentiel avec un exposant linéaire	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}\left(2^{kn}\right)}$
NEXPSPACE	décidable par une machine non déterministe en espace exponentiel	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}\left(2^{n^{k}}\right)}$ ; égale à${\displaystyle {\mbox{ EXPSPACE }}}$par le théorème de Savitch
NEXPTIME (ou NEXP)	décidable par une machine non déterministe en temps exponentiel	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}\left(2^{n^{k}}\right)}$
NL	décidable par une machine non déterministe en espace logarithmique (réponse positive vérifiable en espace logarithmique)	${\displaystyle {\mbox{NSPACE }}(\log(n))}$
NP	décidable par une machine non déterministe en temps polynomial (réponse positive vérifiable en temps polynomial)	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}\left({n^{k}}\right)}$
NP-complet	NP et NP-difficile
NP-difficile	tout problème NP peut s'y ramener par réduction polynomiale
NP-facile	décidable en temps polynomial avec un oracle pour un problème NP
NP-intermédiaire	dans NP, mais ni dans P ni NP-complet
NPSPACE	décidable par une machine non déterministe en espace polynomial	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}\left({n^{k}}\right)}$ ; égale à${\displaystyle {\mbox{ PSPACE }}}$par le théorème de Savitch
NSPACE(f(n))	décidable par une machine non déterministe en espace O(f(n))
NTIME(f(n))	décidable par une machine non déterministe en temps O(f(n))
P	décidable en temps polynomial	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left({n^{k}}\right)}$
P/poly	décidable par une famille de circuits booléens de tailles polynomiales
PH	réunion des classes de la hiérarchie polynomiale
PP	décidable en temps polynomial par une machine de Turing probabiliste avec une probabilité d'erreur inférieure à 1/2
PSPACE	décidable en espace polynomial	${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}\left({n^{k}}\right)}$ ; égale à${\displaystyle {\mbox{ NPSPACE }}}$par le théorème de Savitch
R	décidable	${\displaystyle {\mbox{RE}}\cap {\mbox{co-RE}}}$
RE	récursivement énumérable
RP	décidable en temps polynomial par une machine de Turing probabiliste refusant toutes les instances négatives et acceptant les instances positives avec une probabilité supérieure à 1/2
UP	décidable par une machine de Turing non ambigüe en temps polynomial
ZPP	décidable par une machine de Turing probabiliste en temps polynomial en espérance, sans erreur	${\displaystyle {\mbox{RP}}\cap {\mbox{co-RP}}}$

Bibliographie

• (en) Sanjeev Arora et Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 20 avril 2009, 579 p. (ISBN 978-0-521-42426-4, lire en ligne). 
• Sylvain Perifel, Complexité algorithmique, Éditions Ellipses, 22 avril 2014, 432 p. (ISBN 978-2-729-88692-9, lire en ligne). 

Lien externe

• Complexity Zoo, une liste de plus de 500 classes de complexité et de leurs propriétés