Un espoir vain

Propriété 10.4.4   Si $\Pi$ et $\Pi^\prime$ sont NP-Complets, et qu'il est possible de décider $\Pi$ en temps polynomial, alors on peut décider $\Pi^\prime$ en temps polynomial.

Comme $\Pi^\prime$ appartient à $NP$, alors $\Pi^\prime \leq 3-SAT$, et comme $\Pi$ est NP-Complet, alors $3-SAT \leq \Pi$. Donc $\Pi^\prime \leq \Pi$. Si $\Pi \in P$, alors $\Pi^\prime \in P$.

Cette propriété est très importante, elle signifie que si on parvenait à décider un seul problème NP-Complet en temps polynomial, alors on pourrait tous les décider en temps polynomial et on aurait $P = NP$.