Certificat (algorithmique)
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
En informatique théorique, plus précisément en théorie de la complexité, é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.
