Définition

Nous allons établir une relation d'ordre sur les problèmes, nous la noterons

$$\Pi \leq \Pi^\prime$$

ce qui signifie "$\Pi$ est moins difficile que $\Pi^\prime$". $\leq$ est définie comme suit

Définition 10.3.1   $\Pi \leq \Pi^\prime$ s'il existe une fonction $f$ de complexité polynomiale qui à toute instance $I$ de $\Pi$ associe une instance $I^\prime$ de $\Pi^\prime$ telle que $I$ est à réponse oui si et seulement si $I^\prime$ est à réponse oui.