Un certificat pour la réponse « non » ?

Personne ne le sait, et c'est la réponse honnête.

Pourquoi la définition ne le donne pas. La définition de $\mathsf{NP}$ est asymétrique : elle exige un certificat pour les instances positives seulement. Rien n'oblige les instances négatives à en avoir un.

Ce qu'on sait faire, et qui ne suffit pas. Pour montrer qu'une formule est insatisfiable, on peut donner une réfutation — une dérivation de la clause vide par résolution. C'est bien un certificat vérifiable en temps polynomial en sa propre taille. Mais on ne sait pas borner cette taille par un polynôme en $|\phi |$ : le chapitre chap:logique en donne l'exemple, les formules du pigeonnier, dont toute réfutation par résolution est de taille exponentielle. Le certificat existe donc, mais il peut être trop long pour compter.

Ce que l'exercice révèle. Un problème et son complémentaire ne sont pas de même difficulté du point de vue de $\mathsf{NP}$. On note $\mathsf{co}\text{-}\mathsf{NP}$ la classe des problèmes dont le complémentaire est dans $\mathsf{NP}$, et $\mathsf{NP}=\mathsf{co}\text{-}\mathsf{NP}$ est, comme $\mathsf{P}=\mathsf{NP}$, une question ouverte. Le nom de cette classe n'est pas exigible ; l'asymétrie, elle, doit se voir.

Un contre-exemple utile pour fixer les idées. « Ce graphe est-il biparti ? » est dans $\mathsf{P}$ — un parcours en largeur le décide, chapitre chap:parcours. Il est donc dans $\mathsf{NP}$ et son complémentaire aussi : un problème polynomial est toujours symétrique, puisque l'algorithme rend « oui » ou « non » avec le même effort. L'asymétrie n'apparaît que pour les problèmes qu'on ne sait pas résoudre vite.