Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace. On peut par exemple citer les classes P et NP. Suivant qu'il s'agit de temps et d'espace, de machine déterministes ou non déterministes, on distingue quatre familles principales de classes de complexité : TIME(t(n)) La classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine déterministe. NTIME(t(n)) La classe des problèmes de décision qui peuvent être résolus en temps de l'ordre de grandeur de t(n) sur une machine non déterministe. SPACE(s(n)) La classe des problèmes de décision qui requièrent pour être résolus un espace de l'ordre de grandeur de s(n) sur une machine déterministe. NSPACE(s(n)) La classe des problèmes de décision qui requièrent pour être résolus un espace de l'ordre de grandeur de s(n) sur une machine non déterministe. Les classes en temps classiques sont : P, la classe des problèmes décidés en temps polynomial par une machine déterministe. Ces problèmes sont souvent considérés comme ceux pour lesquels il existe un algorithme efficace (voir la thèse de Cobham) ; NP, la classe des problèmes décidés en temps polynomial par une machine non déterministe (ainsi que la classe complémentaire, co-NP) ; EXPTIME, la classe des problèmes décidés en temps exponentiel par une machine déterministe ; NEXPTIME, la classe des problèmes décidés en temps exponentiel par une machine non-déterministe.