Vous souvenez-vous de ce qu'est un problème NP-complet ? En quoi diffère-t-il de simplement NP ?

NP (temps polynomial non déterministe) est une classe de problèmes pour lesquels la solution peut être vérifiée en temps polynomial. Autrement dit, si vous avez un candidat à la réponse, vous pouvez rapidement vérifier s’il est correct ou non.

Les problèmes NP-complets sont un sous-ensemble de NP qui sont à la fois les plus "difficiles" de cette classe. Si quelqu’un trouvait un algorithme polynomial pour résoudre n’importe quel problème NP-complet, alors tous les problèmes de NP pourraient être résolus en temps polynomial.

Différence principale :

• NP : problèmes dont les solutions peuvent être vérifiées rapidement.
• NP-complet : problèmes dans NP auxquels on peut réduire tout autre problème NP (c’est-à-dire, ils sont les "plus difficiles" dans NP).

Exemple : le problème du clique de taille maximale dans un graphe est NP-complet, et le problème de vérification si un sous-ensemble d’éléments somme à un nombre donné est dans NP.