NP-complet

Une définition du Jargon Français.
Aller à : Navigation, rechercher
Reviser.png Cet article est à revoir. Si le cœur vous en dit...


adjectif.  [mathématique]. Caractérise les types de problèmes pour lesquels le coût d'application d'une méthode connue de résolution parfaite, celle qui livre « la meilleure solution », augmente extrêmement vite avec la taille du cas considéré.

Par coût on désigne ici le volume des ressources nécessaires, par exemple des CPU ou de la mémoire, multiplié par le laps de temps durant lequel elles seront mobilisées. Par taille on désigne le nombre de solutions théoriquement possibles.

En résumé ce coût est au mieux proche et au pire égal à ce que coûte le fait de calculer puis tester toutes les solutions possibles.

Le problème du voyageur de commerce l'est car nul ne sait le résoudre parfaitement (trouver la meilleure solution) sans tester tous les trajets possibles, dont le nombre augmente très vite avec celui des villes.

Les spécialistes disent non déterministe polynomial (polynomial caractérise la fonction exprimant le coût d'une résolution).

Voir aussi AI-complet.