Accueil🇫🇷Chercher

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
AC réunion des classes de la hiérarchie ACi ; égale à
AC0 calculable par un circuit booléen de profondeur constante, de taille polynomiale
ACi calculable par un circuit booléen de profondeur , 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
ELEMENTARY réunion des classes de la hiérarchie exponentielle (en)
ESPACE décidable en espace exponentiel avec un exposant linéaire
EXPSPACE décidable en espace exponentiel ; égale àpar le théorème de Savitch
EXPTIME (ou EXP) décidable en temps exponentiel
IP décidable par un système de preuve interactive égale à
L décidable en espace logarithmique
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 à
NE décidable par une machine non déterministe en espace exponentiel avec un exposant linéaire
NEXPSPACE décidable par une machine non déterministe en espace exponentiel ; égale àpar le théorème de Savitch
NEXPTIME (ou NEXP) décidable par une machine non déterministe en temps exponentiel
NL décidable par une machine non déterministe en espace logarithmique (réponse positive vérifiable en espace logarithmique)
NP décidable par une machine non déterministe en temps polynomial (réponse positive vérifiable en temps polynomial)
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 ; égale à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
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 ; égale àpar le théorème de Savitch
R décidable
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

Bibliographie

Lien externe

  • Complexity Zoo, une liste de plus de 500 classes de complexité et de leurs propriétés
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.