Bonsoir,
J'étudie en ce moment les classes de complexités P et NP. Dans un exercice, un certain problème qui est proposé est identique au problème du sac à dos(entier). On sait qu'une stratégie gloutonne ne permet de résoudre le problème mais que la programmation dynamique le permet. En effet, en utilisant la programmation dynamique, on obtient un algorithme avec une complexité en temps polynomiale.
Juste aprés, on nous demande de trouver le problème de décision équivalent au problème de départ(qui est de type optimisation), ce qui se fait facilement.
Mais ensuite on nous demande de prouver que le problème de décision est NP-complet et ca je ne comprends pas pourquoi.
Résoudre le problème de décision est simple:
1) On utilise l'algorithme de programmation dynamique obtenu plus haut pour obtenir la solution optimale et sa valeur.
2) On compare la valeur obtenu avec le parametre du probleme de décision et on peut répondre alors au problème par oui ou non.
Et tout cela peut se faire en temps polynomial.
Donc je ne comprends plus trop quelle est la différence entre P, NP et NP-complet.

Merci d'avance