En théorie de la complexité, un problème NP-complet ou problème NPC est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement ; 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. Wikipedia