Un peu de complexité
On s’intéresse à la difficulté asymptotique des problèmes algorithmiques.
P = les problèmes dont on peut facilement trouver une solution.
NP = les problèmes dont on peut facilement vérifier une solution.
Il existe des problèmes au moins aussi difficiles que tous ceux de NP : ils sont NP-durs.