Accès plus rapide que le navigateur!
12 relations: BPP (complexité), Classe de complexité, DTIME, EXPTIME, Informatique théorique, Machine de Turing, NP (complexité), Problème de décision, PSPACE, Réduction polynomiale, Symposium on Foundations of Computer Science, Théorie de la complexité (informatique théorique).
BPP (complexité)
En informatique théorique, plus précisément en théorie de la complexité, la classe BPP (bounded-error probabilistic polynomial time) est la classe de problèmes de décision décidés par une machine de Turing probabiliste en temps polynomial, avec une probabilité d'erreur dans la réponse inférieure à 1/3.
Nouveau!!: E (complexité) et BPP (complexité) · Voir plus »
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.
Nouveau!!: E (complexité) et Classe de complexité · Voir plus »
DTIME
En théorie de la complexité, DTIME (ou TIME) désigne une famille de classes de complexité caractérisée par leur complexité en temps sur une machine de Turing déterministe.
Nouveau!!: E (complexité) et DTIME · Voir plus »
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.
Nouveau!!: E (complexité) et EXPTIME · Voir plus »
Informatique théorique
Une représentation artistique d'une machine de Turing. Les machines de Turing sont un modèle de calcul. L'informatique théorique est l'étude des fondements logiques et mathématiques de l'informatique.
Nouveau!!: E (complexité) et Informatique théorique · Voir plus »
Machine de Turing
En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur.
Nouveau!!: E (complexité) et Machine de Turing · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: E (complexité) et NP (complexité) · Voir plus »
Problème de décision
En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ».
Nouveau!!: E (complexité) et Problème de décision · Voir plus »
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.
Nouveau!!: E (complexité) et PSPACE · Voir plus »
Réduction polynomiale
Une réduction polynomiale est un outil d'informatique théorique, plus particulièrement de théorie de la complexité.
Nouveau!!: E (complexité) et Réduction polynomiale · Voir plus »
Symposium on Foundations of Computer Science
La conférence Annual IEEE Symposium on Foundations of Computer Science (abrégé en FOCS) est une conférence scientifique dans le domaine de l’informatique théorique.
Nouveau!!: E (complexité) et Symposium on Foundations of Computer Science · Voir plus »
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.
Nouveau!!: E (complexité) et Théorie de la complexité (informatique théorique) · Voir plus »
