problème NP-complet
COMBINATOIRE
Un problème NP-complet est un problème de décision vérifiant les conditions suivantes :
• Il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP.
• Tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP.
Le concept de NP-complétude a été introduit en 1971 par Stephen Cook dans une communication intitulée La complexité des procédures de démonstration de problèmes.
Parmi les problèmes NP-complets, on peut citer le problème du sac à dos .