Certificat (algorithmique)
- Certificat (algorithmique)
-
En informatique théorique, plus précisément en théorie de la complexité des algorithmes, étant donné un problème de décision, un certificat est une information que l'on ajoute à une donnée du problème pour certifier, au sens où la vérification devient « facile », qu'elle est — ou n'est pas — solution.
En particulier un problème de décision est dans la classe NP s'il existe pour chaque solution positive un certificat polynomial, c'est-à-dire s'il existe pour chaque donnée pour laquelle la réponse est « oui », un certificat de longueur polynomiale en la taille de la donnée, tel que la vérification de la réponse pour la donnée munie de son certificat se réalise en temps polynomial.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Certificat (algorithmique) de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Certificat polynomial — Certificat (algorithmique) En informatique théorique, plus précisément en théorie de la complexité des algorithmes, étant donné un problème de décision, un certificat est une information que l on ajoute à une donnée du problème pour certifier, au … Wikipédia en Français
Complexite algorithmique — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Complexité Algorithmique — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Toile de confiance — En cryptographie, la toile de confiance est un concept utilisé dans PGP, GnuPG, ainsi que d autre systèmes compatibles avec OpenPGP. La toile de confiance permet de vérifier la relation entre une clé publique et son possesseur. C est un modèle de … Wikipédia en Français
Classe NP — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Classe de complexité — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Classes de complexité P et NP — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Complexite P — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Complexité des algorithmes — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
Complexité des classes P et NP — Théorie de la complexité des algorithmes La théorie de la complexité des algorithmes étudie formellement la difficulté intrinsèque des problèmes algorithmiques. Sommaire 1 Histoire 2 Généralités 2.1 Présentation … Wikipédia en Français
