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.

Exemples

Nombre composé

Pour certifier qu'un nombre est composé (i.e. n'est pas premier), il suffit d'exhiber un facteur. Par exemple, pour certifier que 15 est un nombre composé, le nombre 5 est un certificat : il suffit alors de vérifier que 5 divise 15.

Coloration de graphe

Pour vérifier qu'un graphe non orienté est colorable avec trois couleurs, c'est-à-dire que l'on peut colorier chaque sommet d'une couleur de façon que deux sommets voisins ne soient pas de la même couleur, il suffit d'exhiber une telle coloration. Pour certifier qu'un graphe est colorable, une coloration est un certificat : il suffit alors de vérifier que la coloration attribue bien des couleurs différents à deux sommets voisins.

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, 2014, 432 p. (ISBN 9782729886929, lire en ligne), chap. 2.2 (« Temps non déterministe ») p.56.