Table des matières
9 relations: Complexité en espace, EXPSPACE, EXPTIME, Machine de Turing non déterministe, NP (complexité), PSPACE, Théorème de Savitch, Théorie de la complexité (informatique théorique), 2-EXPTIME.
Complexité en espace
En algorithmique, la complexité en espace est une mesure de l'espace utilisé par un algorithme, en fonction de propriétés de ses entrées.
Voir NEXPSPACE et Complexité en espace
EXPSPACE
En théorie de la complexité, EXPSPACE est la classe des problèmes décidables en espace exponentiel par une machine de Turing déterministe.
EXPTIME
En théorie de la complexité, EXPTIME (ou EXP) est la classe de complexité qui est l'ensemble des problèmes de décision décidés par une machine de Turing déterministe en temps exponentiel.
Voir NEXPSPACE et EXPTIME
Machine de Turing non déterministe
Une machine de Turing non déterministe est similaire à une machine de Turing habituelle, qui, elle, est déterministe, mais s'en différencie dans le fait qu'étant non déterministe elle peut avoir plusieurs transitions activables, pour un état donné.
Voir NEXPSPACE et Machine de Turing non déterministe
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Voir NEXPSPACE et NP (complexité)
PSPACE
En informatique théorique, plus précisément en théorie de la complexité, PSPACE est la classe de complexité des problèmes de décision décidés par une machine de Turing déterministe avec un espace polynomial.
Voir NEXPSPACE et PSPACE
Théorème de Savitch
Le théorème de Savitch est un théorème de théorie de la complexité, un domaine de l'informatique théorique.
Voir NEXPSPACE et Théorème de Savitch
Théorie de la complexité (informatique théorique)
P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée…) requis par un algorithme pour résoudre un problème algorithmique.
Voir NEXPSPACE et Théorie de la complexité (informatique théorique)
2-EXPTIME
En informatique théorique, plus précisément en théorie de la complexité, la classe 2-EXPTIME est la classe des problèmes de décision décidés par une machine de Turing déterministe en temps doublement exponentiel, c'est-à-dire en temps O(22p(n)), où p(n) est un polynôme en la taille de l'entrée n.