Somme de sous-ensemble, solution de programmation dynamique temporelle pseudo-polynomiale?

8

J'ai trouvé le problème P vs NP il y a quelque temps et j'ai récemment travaillé sur le problème de la somme des sous-ensembles. J'ai lu un article Wikipédia sur le problème de la sous-somme ainsi que la question Algorithme de la sous-somme

J'ai examiné le problème et trouvé des solutions, mais jusqu'à présent, elles semblent être NP, je crois que je peux faire un algorithme suffisamment rapide en temps NP.

Mon problème est que je ne suis pas bon en théorie, donc cela ne m'aide pas beaucoup de parler du théorème de Cook-Levin ou des machines de Turing non déterministes.

Ce que je voudrais, c'est une explication de la somme du sous-ensemble de programmation dynamique pseudo-polynomiale sur Wikipédia.

Je l'ai lu et je crois comprendre le concept général de la raison pour laquelle il s'agit de NP au lieu de P (lié à la taille de l'entrée plutôt qu'aux opérations avec), mais je ne comprends pas l'algorithme.

J'apprécierais que quelqu'un mette un exemple avec quelques chiffres et comment cela fonctionne. Cela m'aiderait beaucoup car cela:

  • Donnez-moi des idées pour améliorer mon futur algorithme
  • Aidez-moi à comprendre intuitivement quand un algorithme est pseudo-polyonial au lieu de NP.
algorithms dynamic-programming Communauté
la source
1
crab.rutgers.edu/~guyk/ex/part.pdf
Robert Harvey
1
cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/…
Robert Harvey
2
Quelle est la question? Au début, je pensais que vous demandiez un exemple du fonctionnement de l'algorithme auquel vous liez, mais j'ai suivi le lien et il y a déjà un exemple.
rgrig
2
J'ai également du mal à comprendre les messages, ce qui est demandé n'est pas clair. btw, chaque problème dans P est aussi dans NP. Je suppose que vous voulez dire NP-complet au lieu de NP à plusieurs endroits dans votre message. Enfin, il n'est pas logique de dire qu'un algorithme est en NP, NP est une classe de langages et non des algorithmes. Je suppose que vous avez l'idée fausse courante que NP signifie algorithme de temps non polynomial (ou temps exponentiel).
Kaveh
2
Si vous avez lié la taille des valeurs en entrée (lié le nombre de bits pour chaque valeur à être logarithmique dans le nombre total de bits de l'entrée), le problème peut être résolu en temps polynomial en utilisant la programmation dynamique. S'ils ne sont pas limités, ils peuvent avoir des valeurs exponentiellement grandes et la taille de la table pour la programmation dynamique serait exponentielle.
Kaveh

Réponses:

5

Reformulation du commentaire de Kaveh comme réponse:

Si vous avez lié la taille des valeurs en entrée (lié le nombre de bits pour chaque valeur à être logarithmique dans le nombre total de bits de l'entrée), le problème peut être résolu en temps polynomial en utilisant la programmation dynamique. S'ils ne sont pas limités, ils peuvent avoir des valeurs exponentiellement grandes et la taille de la table pour la programmation dynamique serait exponentielle.

jmite
la source