Liste de classes de complexité
# 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 | $\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{2^{n^{k}}}\right)$ |
| AC | réunion des classes de la hiérarchie $AC^i$ | $\bigcup _{i\in \mathbb {N} }{\mbox{AC}}^{i}$ ; égale à ${\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 $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 | $\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{kn}\right)$ |
| ELEMENTARY | réunion des classes de la hiérarchie exponentielle (en) | $\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 | $\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}\left(2^{kn}\right)$ |
| EXPSPACE | décidable en espace exponentiel | $\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}\left(2^{n^{k}}\right)$ ; égale à${\mbox{ NEXPSPACE }}$par le théorème de Savitch |
| EXPTIME (ou EXP) | décidable en temps exponentiel | $\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right)$ |
| IP | décidable par un système de preuve interactive | égale à${\mbox{ PSPACE }}$ |
| L | décidable en espace logarithmique | ${\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 à ${\mbox{AC}}$ |
| NE | décidable par une machine non déterministe en espace exponentiel avec un exposant linéaire | $\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}\left(2^{kn}\right)$ |
| NEXPSPACE | décidable par une machine non déterministe en espace exponentiel | $\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}\left(2^{n^{k}}\right)$ ; égale à${\mbox{ EXPSPACE }}$par le théorème de Savitch |
| NEXPTIME (ou NEXP) | décidable par une machine non déterministe en temps exponentiel | $\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) | ${\mbox{NSPACE }}(\log(n))$ |
| NP | décidable par une machine non déterministe en temps polynomial (réponse positive vérifiable en temps polynomial) | $\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 | $\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}\left({n^{k}}\right)$ ; égale à${\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 | $\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 | $\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}\left({n^{k}}\right)$ ; égale à${\mbox{ NPSPACE }}$par le théorème de Savitch |
| R | décidable | ${\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 | ${\mbox{RP}}\cap {\mbox{co-RP}}$ |
