Accès plus rapide que le navigateur!
19 relations: BPP (complexité), Classe de complexité, Générateur de nombres aléatoires, Hiérarchie polynomiale, Hypothèse de Riemann généralisée, IP (complexité), László Babai, Madhu Sudan, NP (complexité), Oracle (machine de Turing), P/poly, PP (complexité), Preuve à divulgation nulle de connaissance, Problème de décision, Problème de l'isomorphisme de graphes, PSPACE, Système de preuve interactive, Théorème de Sipser-Gács-Lautemann, 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!!: Protocole Arthur-Merlin 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!!: Protocole Arthur-Merlin et Classe de complexité · Voir plus »
Générateur de nombres aléatoires
Un générateur de nombres aléatoires, random number generator (RNG) en anglais, est un dispositif capable de produire une suite de nombres pour lesquels il n'existe aucun lien calculable entre un nombre et ses prédécesseurs, de façon que cette séquence puisse être appelée « suite de nombres aléatoires ».
Nouveau!!: Protocole Arthur-Merlin et Générateur de nombres aléatoires · 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!!: Protocole Arthur-Merlin et Hiérarchie polynomiale · Voir plus »
Hypothèse de Riemann généralisée
L'hypothèse de Riemann est l'une des plus importantes conjectures des mathématiques et concerne les zéros de la fonction ζ de Riemann.
Nouveau!!: Protocole Arthur-Merlin et Hypothèse de Riemann généralisée · Voir plus »
IP (complexité)
En informatique théorique, et notamment en théorie de la complexité, la classe IP (une abréviation pour, c'est-à-dire « interactif en temps polynomial ») est la classe des problèmes de décision qui peuvent être résolus par un système de preuve interactive.
Nouveau!!: Protocole Arthur-Merlin et IP (complexité) · Voir plus »
László Babai
László Babai, né le à Budapest, est un professeur de mathématiques et d'informatique hongrois, enseignant actuellement à l'université de Chicago.
Nouveau!!: Protocole Arthur-Merlin et László Babai · Voir plus »
Madhu Sudan
Madhu Sudan (மதுசூதன்) (Marath: मधु सुदन) (né le) est un informaticien théorique indien, professeur d'informatique au Massachusetts Institute of Technology (MIT) et membre du MIT Computer Science and Artificial Intelligence Laboratory.
Nouveau!!: Protocole Arthur-Merlin et Madhu Sudan · Voir plus »
NP (complexité)
La classe NP est une classe très importante de la théorie de la complexité.
Nouveau!!: Protocole Arthur-Merlin et NP (complexité) · Voir plus »
Oracle (machine de Turing)
Une machine de Turing avec oracle peut faire appel à une boîte noire (oracle). En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire.
Nouveau!!: Protocole Arthur-Merlin et Oracle (machine de Turing) · Voir plus »
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.
Nouveau!!: Protocole Arthur-Merlin et P/poly · Voir plus »
PP (complexité)
PP est un objet de la théorie de la complexité, un domaine de l'informatique théorique.
Nouveau!!: Protocole Arthur-Merlin et PP (complexité) · Voir plus »
Preuve à divulgation nulle de connaissance
Une preuve à divulgation nulle de connaissance est une brique de base utilisée en cryptologie dans le cadre de l'authentification et de l'identification.
Nouveau!!: Protocole Arthur-Merlin et Preuve à divulgation nulle de connaissance · 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!!: Protocole Arthur-Merlin et Problème de décision · Voir plus »
Problème de l'isomorphisme de graphes
Le problème est de savoir si deux graphes sont les mêmes. En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets.
Nouveau!!: Protocole Arthur-Merlin et Problème de l'isomorphisme de graphes · 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!!: Protocole Arthur-Merlin et PSPACE · Voir plus »
Système de preuve interactive
Un système de preuve interactive est composé de deux machines abstraites: un prouveur et un vérificateur qui s'échangent des messages. En théorie de la complexité des algorithmes, un système de preuve interactive est un protocole formel de démonstration de théorèmes qui fait intervenir deux participants qui échangent des messages.
Nouveau!!: Protocole Arthur-Merlin et Système de preuve interactive · Voir plus »
Théorème de Sipser-Gács-Lautemann
En informatique théorique, plus précisément en théorie de la complexité, le théorème de Sipser-Gács-Lautemann (ou théorème de Sipser-Lautemann ou de Sipser-Gács) est le théorème qui énonce que la classe probabiliste BPP (bounded-error probabilistic polynomial time) est incluse dans la hiérarchie polynomiale.
Nouveau!!: Protocole Arthur-Merlin et Théorème de Sipser-Gács-Lautemann · 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!!: Protocole Arthur-Merlin et Théorie de la complexité (informatique théorique) · Voir plus »
