Table des matières
15 relations: Classe de complexité, Complexité en espace, DSPACE, EXPTIME, Liste de classes de complexité, NEXPSPACE, P (complexité), P/poly, Planification (intelligence artificielle), Problème de la hauteur d'étoile, Problème NP-complet, PSPACE, Synthèse de programmes, Théorème de Savitch, Théorie de la complexité (informatique théorique).
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.
Voir EXPSPACE et Classe de complexité
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 EXPSPACE et Complexité en espace
DSPACE
En théorie de la complexité, DSPACE (ou SPACE) désigne une famille de classes de complexité caractérisées par leur complexité en espace sur une machine de Turing déterministe.
Voir EXPSPACE et DSPACE
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 EXPSPACE et EXPTIME
Liste de classes de complexité
Cet article présente une liste de classes de complexité en théorie de la complexité.
Voir EXPSPACE et Liste de classes de complexité
NEXPSPACE
NEXPSPACE est une classe de la théorie de la complexité.
P (complexité)
La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques.
Voir EXPSPACE et P (complexité)
P/poly
En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales.
Voir EXPSPACE et P/poly
Planification (intelligence artificielle)
257x257px En intelligence artificielle, la planification automatique (automated planning en anglais) ou plus simplement planification, vise à développer des algorithmes pour produire des plans typiquement pour l'exécution par un robot ou tout autre agent.
Voir EXPSPACE et Planification (intelligence artificielle)
Problème de la hauteur d'étoile
Le problème de la hauteur d'étoile, en théorie des langages formels, est le problème qui consiste à déterminer la hauteur d'étoile d'un langage rationnel, c'est-à-dire le nombre minimal d'étoiles de Kleene imbriquées nécessaires dans une expression rationnelle pour qu'elle puisse dénoter ce langage.
Voir EXPSPACE et Problème de la hauteur d'étoile
Problème NP-complet
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes.
Voir EXPSPACE et Problème NP-complet
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 EXPSPACE et PSPACE
Synthèse de programmes
En informatique, la synthèse de programmes consiste à construire automatiquement un programme à partir d'une spécification.
Voir EXPSPACE et Synthèse de programmes
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 EXPSPACE 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 EXPSPACE et Théorie de la complexité (informatique théorique)