Application

Propriété 10.3.1   Si $\Pi \leq \Pi^\prime$ et $\Pi^\prime \in P$, alors $\Pi \in P$.

Soit $I$ une instance de $\Pi$, comme $\Pi \leq \Pi^\prime$, alors il existe $f$ polynomiale telle que $I$ est à réponse oui si et seulement si $f(I)$ est à réponse oui. Comme $\Pi^\prime \in P$, alors $\Pi^\prime$ est décidé par un algorithme polynomial. En appliquant cet algorithme à $f(I)$, on décide $I$. L'algorithme qu'on obtient est donc

• Déterminer $f(I)$ (polynomial)
• Décider $f(I)$ (polynomial)

Comme les deux algorithmes considérés sont polynomiaux, alors $I$ est décidé en temps polynomial. Donc $\Pi \in P$.

Il est important de retenir que $\Pi \leq \Pi^\prime$ implique que l'existence d'un algorithme polynomial décidant $\Pi^\prime$ implique l'existence d'un algorithme polynomial décidant $\Pi$.