En gros : P, c'est l'ensemble des problèmes que l'on peut résoudre en temps polynômial (i.e. dont le temps de résolution est majoré par une fonction polynômiale de la taille des paramètres), et NP ceux que l'on peut résoudre en temps exponentiel (exemple : à partir d'une expression logique à N variables, trouver des valeurs de vérité qui satisfont l'expression).
On a donc l'inclusion P c NP, mais l'on se demande si l'inclusion est stricte ou s'il s'agit d'une égalité. Dans le second cas, cela signifie qu'il est possible de traiter tout problème de complexité exponentielle en temps polynômial (en réduisant le problème à un autre problème par exemple). Cela aurait pour conséquence d'affaiblir de nombreux protocoles de chiffrement, signatures, etc. qui se basent sur le fait que "casser la clé" revienne à résoudre un problème NP particulier (pour lequel on a encore aucun algorithme en temps polynômial).
Mais si l'inclusion est stricte, ça nous donne une garantie sur la sûreté des algorithmes de chiffrement/déchiffrement : si l'attaque se fait par cassage de clé, elle se fera en temps exponentiel. Il suffit donc de calibrer la taille de la clé pour que le temps nécessaire à la casser soit supérieur à sa durée de vie.
[^] # Re: Mais ké kidi?
Posté par Samuel (site web personnel) . En réponse au journal P != NP : la preuve. Évalué à 8.
On a donc l'inclusion P c NP, mais l'on se demande si l'inclusion est stricte ou s'il s'agit d'une égalité. Dans le second cas, cela signifie qu'il est possible de traiter tout problème de complexité exponentielle en temps polynômial (en réduisant le problème à un autre problème par exemple). Cela aurait pour conséquence d'affaiblir de nombreux protocoles de chiffrement, signatures, etc. qui se basent sur le fait que "casser la clé" revienne à résoudre un problème NP particulier (pour lequel on a encore aucun algorithme en temps polynômial).
Mais si l'inclusion est stricte, ça nous donne une garantie sur la sûreté des algorithmes de chiffrement/déchiffrement : si l'attaque se fait par cassage de clé, elle se fera en temps exponentiel. Il suffit donc de calibrer la taille de la clé pour que le temps nécessaire à la casser soit supérieur à sa durée de vie.