Réductions polynomiales

Soit $\Pi$ un problème de $NP$ pour lequel vous ne parvenez pas à trouver d'algorithme polynomial, vous nous pouvez pas dire que ce problème n'est pas dans $P$, car vous ne savez pas si $NP \setminus P$ est vide ou non. Il va donc falloir procéder autrement. Nous allons introduire la notion de difficulté d'un problème, ainsi qu'un moyen de comparer des problèmes.