Discussion :

[Miko95]

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

[Nemerle]

http://interstices.info/jcms/c_39182...de-sy-attaquer

[Miko95]

Merci pour le lien mais je ne vois pas en quoi ca répond à la question.
D'après l'article, j'ai bien compris qu'un problème qui est NP-Complet est aussi NP(c'est une des deux conditions pour qu'un problème soit NP-Complet). Mais dans le cas du problème de sac à dos, on a un algorithme utilisant la programmation dynamique qui résous le problème en temps polynomial et il devrait être P et non NP, je me trompe?

[pseudocode]

Mais dans le cas du problème de sac à dos, on a un algorithme utilisant la programmation dynamique qui résous le problème en temps polynomial et il devrait être P et non NP, je me trompe?

? En temps polynomial par rapport a quoi ?

- au nombre d'éléments ? si oui, tu es millionnaire.

- au poids max du sac ? Ah, c'est déjà connu. Pas de bol.

[Jimmy_]

Tu confonds théorie des algorithmes et méthode de résolution d'un problème.

Le problème du sac à dos est NP-Complet il a été étudié à de maint reprise.
Il existe des algorithmes pour le résoudre, la programmation dynamique est l'un d'eux.
La solution naive produit un algorithme de complexité exponentielle car teste toutes les solutions.
La programmation dynamique produit un algorithme de complexité polynomial en optimisant les tests.

[j-jorge]

Mais dans le cas du problème de sac à dos, on a un algorithme utilisant la programmation dynamique qui résous le problème en temps polynomial et il devrait être P et non NP, je me trompe?

La programmation dynamique produit un algorithme de complexité polynomial en optimisant les tests.

Les algorithmes utilisant la programmation dynamique ont une complexité pseudo-polynomiale : O(nW) avec n le nombre d'objets et W la capacité du sac. C'est différent d'un algorithme polynomial et on peut voir que ça reste coûteux sur certaines instances. En particulier, l'article Where are the Hard Knapsack Problems de D. Pisinger présente des instances du problème mettant à genoux de très bons algorithmes.