Non-deterministe Polynomial : on a un algo polynomial qui dit si une solution est bonne ou pas.
Exemple sur le voyageur de commerce : si on lui donne un chemin, il est capable de dire en temps polynomial si cette solution est la meilleur solution (polynomial, ca peux etre affreux, mais pas exponentiel).
Par contre, pour trouver LE meilleur chemin, il faudrait generer tout les chemins (en nombre exponentiel) et les tester.
Le NP-complet veux en gros dire (c'est bien compliqué en fait...) qu'il n'existe pas d'algo polynomiaux resolvant le probleme (dans le cas général).
[^] # Re: Algorithme génétique ?
Posté par TeXitoi (site web personnel) . En réponse à la dépêche Améliorer les performances du noyau avec un algorithme génétique. Évalué à 3.
Pour expliquer en gros ce que ca veux dire:
Non-deterministe Polynomial : on a un algo polynomial qui dit si une solution est bonne ou pas.
Exemple sur le voyageur de commerce : si on lui donne un chemin, il est capable de dire en temps polynomial si cette solution est la meilleur solution (polynomial, ca peux etre affreux, mais pas exponentiel).
Par contre, pour trouver LE meilleur chemin, il faudrait generer tout les chemins (en nombre exponentiel) et les tester.
Le NP-complet veux en gros dire (c'est bien compliqué en fait...) qu'il n'existe pas d'algo polynomiaux resolvant le probleme (dans le cas général).