problème NP-complet
- Domaine
-
- intelligence artificielle
- Dernière mise à jour
Définition :
Problème complexe de grande taille dont les solutions par des algorithmes déterministes conduisent à des calculs exponentiels. Un problème est dit NP-complet (ou Non déterministe Polynomial complet) lorsqu'il appartient à la classe des problèmes NP et lorsqu'il est réductible, à une transformation polynomiale près, au problème de la satisfiabilité d'une expression logique (problème archétype de la classe NP).
Note :
Le problème qui consiste à déterminer si une expression booléenne sous forme conjonctive normale peut être satisfaite par un énoncé de vérité, est le premier problème NP complet qui a été trouvé; ceci est généralement appelé « problème de satisfiabilité » ou (satisfiabilité de FCN}. En dépit d'un effort considérable, il n'a pas encore été démontré que l'un des problèmes NP complets puisse être résolu de façon polynomiale. Il est donc largement conjecturé qu'aucun problème NP complet ne peut l'être.
Termes privilégiés :
- problème NP-complet n. m.
- problème non déterministe polynomial complet n. m.
Traductions
-
anglais
Auteur : Office québécois de la langue française,Termes :
- NP-complete problem
- non-deterministic polynomial time complete problem