La classe NP

Etant donné un problème de décision, ce problème est dans NP s'il est possible de vérifier une solution en temps polynomial. Considérons par exemple le problème suivant :

• Données : un graphe $G$
• Question : existe-t-il un cycle hamiltonien dans $G$ ?

Supposons que ce graphe contienne $100$ sommets, et qu'un de vos camarade vous dise : "cette instance est à réponse oui". Vous lui demanderez certainement : "dans quel ordre parcourir les sommets pour former un cycle hamiltonien" ? Notez bien que malgré le fait que résoudre le problème soit infaisable en pratique, vérifier qu'un chemin est effectivement un chemin hamiltonien est très aisé. Un cycle permettant de vérifier en temps polynomial qu'une telle instance est une instance à réponse oui s'appelle un certificat.

Plus généralement, étant donné une instance $I$ d'un problème $\Pi$, un certificat $c$ est une donnée permettant de vérifier en temps polynomial que $I$ est une instance de $\Pi$ à réponse oui.