Certificat polynomial
- 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 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.
Portail de l’informatique
Catégorie : Algorithmique
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Certificat polynomial de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
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… … 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
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
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
NP-Complet — 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
