Discussion :

[mido1951]

bonjour,
est-ce que je peux avoir la différence entre la compléxité NP-Difficile et NP-Complet? et je peux avoir un exemple dans chaque cas??
merci

[pseudocode]

Problèmes de la classe NP = problèmes qui peuvent être résolus en utilisant une machine de turing non-déterministe, dans un temps polynomial (par rapport à la taille des entrées).

Problèmes de la classe NP-Complet = problèmes les plus "généraux" de NP. Autrement dit, tout problème de NP (et de P) peut être vu comme un cas particulier d'un problème NP-Complet.

Problèmes de la classe NP-Hard = problèmes qui sont aussi compliqués, ou encore plus compliqués, qu'un problème NP-Complet.