Probleme – SAT : vérifier est facile, chercher ne l'est pas

1. L'exhaustif. Une formule en forme normale conjonctive sur $n$ variables et $m$ clauses. On énumère les $2^n$ valuations.

pour chaque entier k de 0 a 2^n - 1
    val <-- les n bits de k
    si toutes les clauses sont satisfaites par val
        alors rendre val
rendre "insatisfiable"

Terminaison : la boucle est bornée. Correction : on essaie toutes les valuations ; si aucune ne convient, il n'y en a pas. Complexité : $\Theta (2^n\cdot |\phi |)$ dans le pire cas — atteint exactement quand la formule est insatisfiable, puisqu'il faut alors aller au bout.

2. Le vérificateur.

verifier(phi, val) :
    pour chaque clause de phi
        si aucun litteral de la clause n'est vrai sous val
            alors rendre faux
    rendre vrai

Complexité : $\Theta (|\phi |)$ — une lecture de la formule. Le certificat est la valuation, soit $n$ bits : de taille linéaire en l'entrée. Les deux conditions de la définition de $\mathsf{NP}$ sont donc remplies, et sat $\in \mathsf{NP}$.

3. Les mesures. Sur des formules $3$-fnc aléatoires à $m=4n$ clauses :

Trois lectures.

• Le temps de recherche double à chaque variable ajoutée. De $n=20$ à $n=22$, il est multiplié par $16$ — l'instance était en outre insatisfiable, donc parcourue en entier.
• Le temps de vérification ne bouge pas : quelques dizaines de microsecondes, proportionnelles à la taille de la formule et non à $2^n$. Le rapport est de $1$ à $30000$ dès $n=20$. (Les deux instances insatisfiables n'ont pas de certificat à vérifier : la colonne y est vide.)
• Les cas satisfiables s'arrêtent souvent tôt — $289227$ valuations essayées sur $1048576$ pour $n=20$ —, mais c'est de la chance, pas une garantie : le pire cas reste $2^n$.

Cet écart est la question $\mathsf{P}=\mathsf{NP}$, rendue mesurable : la colonne de droite est polynomiale, celle de gauche ne l'est pas, et personne ne sait si l'on peut rapprocher les deux.

4. Les conséquences d'un algorithme polynomial pour sat. Elles sont considérables, et il faut les énoncer précisément.

• Par Cook-Levin, tout problème de $\mathsf{NP}$ se réduit polynomialement à sat. On aurait donc $\mathsf{P}=\mathsf{NP}$ : tous les problèmes à certificat vérifiable deviendraient résolubles vite.
• Toutes les optimisations dont la version décision est dans $\mathsf{NP}$ suivraient, par la dichotomie sur le seuil.
• Les fondements de la cryptographie à clé publique s'effondreraient — la sécurité y repose sur l'idée qu'on vérifie facilement ce qu'on ne trouve pas.

Et une conséquence moins souvent dite, qui vaut d'être retenue : trouver une démonstration mathématique de longueur bornée deviendrait aussi facile que la vérifier. C'est la raison profonde pour laquelle presque tout le monde conjecture que $\mathsf{P}\ne \mathsf{NP}$.