(très grossièrement, un problème est dit NP-complet si on ne sait pas montrer qu'il est au mieux exponentiel ou polynomial ; actuellement, on ne dispose que d'algorithme exponentiel pour les résoudre et comme ils sont dans une même classe d'équivalence, dès q'un tombe, tout le reste suit).
[^] # Re: Un nouvel algo de compression ?
Posté par Olivier Dupuis . En réponse à la dépêche Un nombre premier exécutable ... illégal ?. Évalué à 0.
Voir pour plus d'info sur la complexité de ce problème et des résultat en temps de calcul :
http://dept-info.labri.u-bordeaux.fr/~betrema/deug/poly/premiers.ht(...)
(très grossièrement, un problème est dit NP-complet si on ne sait pas montrer qu'il est au mieux exponentiel ou polynomial ; actuellement, on ne dispose que d'algorithme exponentiel pour les résoudre et comme ils sont dans une même classe d'équivalence, dès q'un tombe, tout le reste suit).