title: Liste de classes de complexité
text: # 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}}$ |
  