NP pour faire simple signifie que le calcul peut être fait en temps polynomial par une machine non deterministe. Concrètement cela signifie que si on peut vérifier la réponse à une problème rapidement alors ce problème est dans NP.
Exemple, vérifier que 15 = 3 * 5 est trivial (une multiplication), par contre l’opération de factorisation est plus difficile.
Il ne faut pas confondre NP et NP-complet. Les problèmes NP-complet sont les problèmes les plus difficile de la classe NP. Si P≠NP alors ces problèmes seront officielement difficile. Mais si P=NP cela signifie qu’à partir du moment on l’on peut vérifier la réponse rapidement, alors le problème est rapide à résoudre, dans tous les cas.
Aujourd’hui on sait si P≠NP alors la factorisation n’est pas dans NP (il y a des problèmes plus dur à résoudre et si on trouve un algo rapide de factorisation cela ne mettra pas en danger la crypto asymétrique dans son ensemble), mais pour autant comme pour les autres problème de la classe NP, on ne connait pas d’algo polynomial.
[^] # Re: Pas convaincu
Posté par Diagonale de Cantor (site web personnel) . En réponse à la dépêche Jericho Chat - Chiffrement incassable utilisant les masques jetables. Évalué à 6.
Depuis la définition de NP :)
NP pour faire simple signifie que le calcul peut être fait en temps polynomial par une machine non deterministe. Concrètement cela signifie que si on peut vérifier la réponse à une problème rapidement alors ce problème est dans NP.
Exemple, vérifier que 15 = 3 * 5 est trivial (une multiplication), par contre l’opération de factorisation est plus difficile.
Il ne faut pas confondre NP et NP-complet. Les problèmes NP-complet sont les problèmes les plus difficile de la classe NP. Si P≠NP alors ces problèmes seront officielement difficile. Mais si P=NP cela signifie qu’à partir du moment on l’on peut vérifier la réponse rapidement, alors le problème est rapide à résoudre, dans tous les cas.
Aujourd’hui on sait si P≠NP alors la factorisation n’est pas dans NP (il y a des problèmes plus dur à résoudre et si on trouve un algo rapide de factorisation cela ne mettra pas en danger la crypto asymétrique dans son ensemble), mais pour autant comme pour les autres problème de la classe NP, on ne connait pas d’algo polynomial.
En espérant avoir été clair.