Le certificat vide

La démonstration. Soit $A\in \mathsf{P}$, résolu par un algorithme $\mathcal{A}$ polynomial. On construit un vérificateur $V$ pour $A$ : $V(x,c)$ ignore le certificat $c$ et rend $\mathcal{A}(x)$.

• Si $x$ est une instance positive, le certificat vide convient — il est bien de taille polynomiale, et $V(x,\epsilon )=\text{vrai}$.
• Si $x$ est négative, $V(x,c)$ est faux pour tout $c$.
• $V$ s'exécute en temps polynomial, puisque $\mathcal{A}$ l'est.

Donc $A\in \mathsf{NP}$.

Premier sens de la faute. $\mathsf{NP}$ ne veut pas dire « non polynomial » : $\mathsf{P}\subseteq \mathsf{NP}$, donc tout problème polynomial est dans $\mathsf{NP}$. Le tri, la connexité d'un graphe, le plus court chemin sont dans $\mathsf{NP}$.

Second sens de la faute. Le n vient de « non déterministe », qui est le vocabulaire d'un modèle de calcul que le programme écarte explicitement. La définition retenue — un certificat vérifiable en temps polynomial — n'en dit rien et suffit à tout.

La bonne lecture, en une phrase : $\mathsf{NP}$ est la classe des problèmes dont on reconnaît une solution quand on la voit. Que l'on sache la trouver est une autre question, et c'est la question ouverte.