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
Version imprimable
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
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.
http://upload.wikimedia.org/wikipedi...p-hard.svg.png