Accès plus rapide que le navigateur!
17 relations: BPP (complexité), Circuit booléen, Classe de complexité, Conseil (informatique théorique), EXPSPACE, Hiérarchie polynomiale, Informatique théorique, Langage creux, Langage unaire, Leonard Adleman, NP (complexité), P (complexité), Problème de décision, Problème P ≟ NP, PSPACE, Théorème de Karp-Lipton, 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!!: P/poly et BPP (complexité) · Voir plus »
Circuit booléen
Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles.
Nouveau!!: P/poly et Circuit booléen · 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!!: P/poly et Classe de complexité · Voir plus »
Conseil (informatique théorique)
En théorie de la complexité, un conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage.
Nouveau!!: P/poly et Conseil (informatique théorique) · Voir plus »
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.
Nouveau!!: P/poly et EXPSPACE · Voir plus »
Hiérarchie polynomiale
En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP.
Nouveau!!: P/poly et Hiérarchie polynomiale · 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!!: P/poly et Informatique théorique · Voir plus »
Langage creux
En théorie de la complexité, un langage creux est un langage où le nombre de mots de longueur n est borné par un polynôme en n. Ils sont utiles dans l'étude de la classe NP.
Nouveau!!: P/poly et Langage creux · Voir plus »
Langage unaire
En théorie des langages, en théorie de la complexité, un langage unaire est un langage qui ne contient que des mots sur une seule et même lettre, généralement notée 1.
Nouveau!!: P/poly et Langage unaire · Voir plus »
Leonard Adleman
Leonard Max Adleman, né le, est un chercheur américain en informatique théorique et professeur en informatique et en biologie moléculaire à l’université de la Californie du Sud.
Nouveau!!: P/poly et Leonard Adleman · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: P/poly et NP (complexité) · Voir plus »
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.
Nouveau!!: P/poly et P (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!!: P/poly et Problème de décision · Voir plus »
Problème P ≟ NP
Représentation visuelle des deux configurations possibles. Le problème est une conjecture en mathématiques, et plus précisément en informatique théorique, considérée par de nombreux chercheurs comme une des plus importantes conjectures du domaine, et même des mathématiques en général.
Nouveau!!: P/poly et Problème P ≟ NP · 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!!: P/poly et PSPACE · Voir plus »
Théorème de Karp-Lipton
En théorie de la complexité, le théorème de Karp–Lipton affirme que si le problème de satisfiabilité booléenne (SAT) est résolu par une famille de circuits booléens avec un nombre polynomial de portes logiques (en la taille de la formule propositionnelle à tester), alors la hiérarchie polynomiale s’effondre au second niveau.
Nouveau!!: P/poly et Théorème de Karp-Lipton · 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!!: P/poly et Théorie de la complexité (informatique théorique) · Voir plus »
