Par ailleurs NP-Complet ne veut pas dire impossible dans le cas moyen.
Le problème de 3-coloration d'un graphe est NP-Complet mais, en moyenne, il requiert 197 operations.
Oui, 197, quelque soit la taille du graphe, i.e. un O(1).
Pour les histoires de securité il faut donc faire des études probabilistes et plein de trucs compliqués.
[^] # Re: Mais ké kidi?
Posté par Oscar Blumberg . En réponse au journal P != NP : la preuve. Évalué à 4.
Le problème de 3-coloration d'un graphe est NP-Complet mais, en moyenne, il requiert 197 operations.
Oui, 197, quelque soit la taille du graphe, i.e. un O(1).
Pour les histoires de securité il faut donc faire des études probabilistes et plein de trucs compliqués.