Cet article présente une liste de classes de complexité en théorie de la complexité. +ClasseDescriptionRelation#Pcompte les solutions d'un problème de NP#P-complet#P et tout problème #P peut s'y ramener par réduction polynomiale2-EXPTIMEdécidable en temps doublement exponentielACréunion des classes de la hiérarchie AC ; égale à ACcalculable par un circuit booléen de profondeur constante, de taille polynomialeACcalculable par un circuit booléen de profondeur , de taille polynomialeALLtous les problèmes de décisionAMdécidable en temps polynomial par un protocole Arthur-Merlin à deux messagesAPXexistence d'un algorithme d'approximation en temps polynomial avec un ratio d'approximation constantBPPdécidable en temps polynomial par une machine de Turing probabiliste avec une probabilité d'erreur inférieure à 1/3BQPdécidable en temps polynomial par un calculateur quantique avec une probabilité d'erreur inférieure à 1/3co-NPréponse négative vérifiable en temps polynomialco-NP-completco-NP et tout problème co-NP peut s'y ramener par réduction polynomialeDSPACE(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))Edécidable en temps exponentiel avec un exposant linéaireELEMENTARYréunion des classes de la ESPACEdécidable en espace exponentiel avec un exposant linéaireEXPSPACEdécidable en espace exponentiel ; égale àpar le théorème de SavitchEXPTIME (ou EXP)décidable en temps exponentielIPdécidable par un système de preuve interactiveégale àLdécidable en espace logarithmiqueLOGCFLréductible en espace logarithmique à un langage hors-contexteNCdécidable en temps polylogarithmique par un nombre polynomial de machines en parallèleégale à NEdécidable par une machine non déterministe en espace exponentiel avec un exposant linéaireNEXPSPACEdécidable par une machine non déterministe en espace exponentiel ; égale àpar le théorème de SavitchNEXPTIME (ou NEXP)décidable par une machine non déterministe en temps exponentielNLdécidable par une machine non déterministe en espace logarithmique (réponse positive vérifiable en espace logarithmique)NPdécidable par une machine non déterministe en temps polynomial (réponse positive vérifiable en temps polynomial)NP-completNP et NP-difficileNP-difficiletout problème NP peut s'y ramener par réduction polynomialeNP-faciledécidable en temps polynomial avec un oracle pour un problème NPNP-intermédiairedans NP, mais ni dans P ni NP-completNPSPACEdécidable par une machine non déterministe en espace polynomial ; égale àpar le théorème de SavitchNSPACE(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))Pdécidable en temps polynomialP/polydécidable par une famille de circuits booléens de tailles polynomialesPHréunion des classes de la hiérarchie polynomialePPdécidable en temps polynomial par une machine de Turing probabiliste avec une probabilité d'erreur inférieure à 1/2PSPACEdécidable en espace polynomial ; égale àpar le théorème de SavitchRdécidableRErécursivement énumérableRPdé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/2UPdécidable par une machine de Turing non ambigüe en temps polynomialZPPdé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
Catégorie:Théorie de la complexité des algorithmes Classes complexite