Conséquences déprimantes

Propriété 10.4.1   Si $\Pi \leq \Pi^\prime$ et $\Pi^\prime \leq \Pi^{\prime\prime}$, alors $\Pi \leq \Pi^{\prime\prime}$.

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 \leq \Pi^{\prime\prime}$, alors il existe $g$ polynomiale telle que $f(I)$ est à réponse oui si et seulement si $(g \circ f)(I)$ est à réponse oui. Donc la réduction $(g \circ f)$ est polynomiale et $I$ est à réponse oui si et seulement si $(g \circ f)(I)$ est à réponse oui.

Définition 10.4.1   $\Pi$ est NP-Complet si pour tout problème $\Pi^\prime \in NP$, on a $\Pi^\prime \leq \Pi$

Autrement dit, $\Pi$ est NP-Complet s'il est plus difficile que n'importe quel problème de $NP$.

Propriété 10.4.2   Si $3-SAT \leq \Pi$, alors $\Pi$ est NP-Complet.

Pour tout $\Pi^\prime \in NP$, $\Pi^\prime \leq 3-SAT$ et $3-SAT \leq \Pi$, donc $\Pi^\prime \leq \Pi$. Alors pour tout $\Pi^\prime \in NP$, $\Pi^\prime \leq \Pi$, donc $\Pi$ est NP-Complet.

Propriété 10.4.3   Si $\Pi$ est NP-Complet, et $\Pi \leq \Pi^\prime$, alors $\Pi^\prime$ est NP-Complet.

Si $\Pi$ est NP-Complet, alors pour tout problème $\Pi^{\prime\prime} \in NP$, $\Pi^{\prime\prime} \leq \Pi$. Comme de plus $\Pi \leq \Pi^\prime$, alors pour tout problème $\Pi^{\prime\prime} \in NP$, $\Pi^{\prime\prime} \leq \Pi^\prime$. Donc $\Pi^\prime$ est NP-Complet.

Si vous voulez montrer qu'un problème est NP-Complet, il suffit de montrer qu'il est plus difficile qu'un problème déjà connu comme étant NP-Complet.