Lire une réduction dans le bon sens

La faute est le sens de la réduction. Il a construit $B{\le }_{p}sat$, et cela signifie : sat est au moins aussi difficile que $B$. Rien sur la difficulté de $B$.

Ce qu'il a démontré, et ce n'est pas rien : $B\in \mathsf{NP}$. Car si l'on sait traduire toute instance de $B$ en une formule équivalente en temps polynomial, alors le certificat de $B$ est la valuation qui satisfait la formule traduite : on la vérifie en temps polynomial en traduisant puis en évaluant. Il a donc prouvé l'appartenance, pas la difficulté.

Ce qu'il aurait fallu écrire : $sat{\le }_{p}B$. C'est-à-dire traduire toute formule en une instance de $B$, de sorte que la formule soit satisfiable si et seulement si l'instance est positive. Alors, savoir résoudre $B$ vite donnerait un algorithme rapide pour sat, donc pour tout $\mathsf{NP}$.

Deux formulations à retenir, et elles disent la même chose :

• $A{\le }_{p}B$ se lit « $A$ n'est pas plus difficile que $B$ ». La flèche va du facile vers le difficile.
• Pour prouver qu'un problème est difficile, on réduit un problème connu difficile vers lui. Pour prouver qu'il est facile, on le réduit vers un problème connu facile.

Et le moyen mnémotechnique le plus sûr : la réduction transporte l'algorithme de la cible vers la source, et la difficulté de la source vers la cible. Elles vont en sens inverse, ce qui est la raison même de la confusion.

Ainsi, un problème np-complet est celui pour lequel les deux réductions existent : $sat{\le }_{p}B$ (il est difficile) et $B{\le }_{p}sat$ (il est dans $\mathsf{NP}$).