Oui, mais parfois le problème est exponentiel dans l'absolu, mais linéaire dans la pratique (ie: dans la quasi-majorité des cas) ou à une petite approximation près.
Dans le premier cas, on peut utiliser un algorithme aléatoire pour gommer l'apparition du pire des cas. (Ce ne sera par exemple pas exploitable par un pirate voulant tenter un DOS.)
Exemple de problème pour le deuxième cas :
* soient deux disques durs de capacité N chacun. On a tout un tas de programmes de taille Ni (Ni = 75 To pour i=emacs par exemple).
Combient peut-on stocker au maximum de programmes sur ses disques ?
On laisse comme exercice au lecteur de démontrer que :
1) ce problème est NP-dur
2) il y a une solution triviale qui se calcule en temps linéaire et qui donne le bon résultat à 1 près.
[^] # NP vs linéaire
Posté par jmfayard . En réponse à la dépêche Comparaison de neuf langages sur un micro-benchmark. Évalué à 2.
Dans le premier cas, on peut utiliser un algorithme aléatoire pour gommer l'apparition du pire des cas. (Ce ne sera par exemple pas exploitable par un pirate voulant tenter un DOS.)
Exemple de problème pour le deuxième cas :
* soient deux disques durs de capacité N chacun. On a tout un tas de programmes de taille Ni (Ni = 75 To pour i=emacs par exemple).
Combient peut-on stocker au maximum de programmes sur ses disques ?
On laisse comme exercice au lecteur de démontrer que :
1) ce problème est NP-dur
2) il y a une solution triviale qui se calcule en temps linéaire et qui donne le bon résultat à 1 près.