Certificat (complexité)

En informatique théorique, plus précisément en théorie de la complexité des algorithmes, un certificat est, de façon simplifiée, une information permettant de certifier que l'entrée est correcte.

Définition

É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 »), que la réponse au problème pour cette donnée soit « oui » ou « non ».

Exemple avec la classe NP

En particulier un problème de décision est dans la classe NP s'il existe pour chaque donnée ayant une réponse 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[1].

Notes et références
  1. Sylvain Perifel, Complexité algorithmique, Ellipses, , 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.2 (« Temps non déterministe ») p.56.
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.