Pourquoi le problème de sac-à-dos pseudo-polynomial?

Question

Je sais qu' Knapsack est NP-complet, même si elle peut être résolu par la DP. Ils disent que le DP solution est - pseudo-polynomial, puisque c'est exponentiel dans la "longueur de l'entrée" (c'est à dire le nombre de bits nécessaires pour coder l'entrée). Malheureusement, je n'ai pas l'obtenir. Quelqu'un peut-il expliquer qu' pseudo-polynomial chose pour moi lentement ?

Answer 1

Le temps d'exécution est O(NW) pour une surabondance de problème de sac-à-dos avec N éléments et sac à dos de taille W. W n'est pas polynomial en la longueur de l'entrée, ce qui est ce qui le rend pseudo-polynomial.

Considérons W = 1,000,000,000,000. Il ne prend que 40 bits pour représenter ce nombre, de sorte que l'entrée size = 40, mais le calcul de l'exécution utilise le facteur de 1,000,000,000,000 qui est O(2^{à 40}).

Si le moteur d'exécution est plus exactement dit à O(N. 2^{bits en W}), qui est exponentielle.

Voir aussi:

• Comment comprendre le problème de sac-à-dos est un problème NP-complet?
• La NP-Complétude de sac à Dos
• La complexité de l'algorithme de programmation dynamique pour le 0-1 problème de sac-à-dos
• Pseudo-polynomial en temps

Answer 2

Dans la plupart de nos problèmes, nous allons travailler avec de grandes listes de nombres qui s'adapte confortablement à l'intérieur de la norme int/float types de données. En raison de la façon dont la plupart des processeurs sont conçus pour gérer de 4 à 8 octets à un moment, sans frais supplémentaires (par rapport à nombre de, disons, 1 octet), il est rare de rencontrer un changement dans la gestion du temps de mise à l'échelle de nos numéros vers le haut ou vers le bas à l'intérieur des plages de nous rencontrer de vrais problèmes - de sorte que le facteur dominant reste juste la quantité de points de données, la n ou m facteurs auxquels nous sommes habitués.

(Vous pouvez imaginer que le Big-O notation se cache un facteur constant qui divise-32 ou 64 bits par donnée, ne laissant que le nombre de points à chaque fois que chacun de nos numéros en nombre de bits ou moins)

Mais essayer de retravailler avec d'autres algorithmes d'agir sur des ensembles de données liée à de gros ints - numéros besoin de plus de 8 octets pour représenter et voir ce que cela donne pour le moment de l'exécution. L'ampleur du nombre de toujours fait une différence, même dans les autres algorithmes comme de tri binaire, une fois que vous développez au-delà de la zone tampon de sécurité les processeurs conventionnels nous donner des "gratuits" par la manipulation de 4 à 8 octets lots.

Le truc avec le sac à Dos de l'algorithme que nous avons discuté est qu'il est particulièrement sensibles (par rapport à d'autres algorithmes ) à l'importance d'un paramètre particulier, W. Ajouter un peu de W et on double le temps d'exécution de l'algorithme. Nous n'avons pas vu ce genre de dramatique réponse à des changements de valeur dans d'autres algorithmes avant de celui-ci, qui est pourquoi il peut sembler que nous allons traiter à Dos différemment - mais c'est une véritable analyse de la façon dont elle répond à un non-polynomiale de la mode à des changements dans la taille de l'image.

Answer 3

Le sac à Dos de l'algorithme d'exécution est lié non seulement sur la taille de l'entrée (n - le nombre d'éléments), mais aussi sur l'ampleur de l'entrée (W - le sac à dos de capacité) O(nW) qui est exponentiel dans la façon dont il est représenté dans l'ordinateur en binaire (2^n) .La complexité de calcul (j'.e la façon dont le traitement est fait à l'intérieur d'un ordinateur par le biais bits) ne concerne que la taille des entrées, pas leurs magnitudes/valeurs.

Abstraction de la valeur de poids/de la liste pour un moment. Disons que nous avons un exemple avec le dos de la capacité 2. W prendrait deux bits dans les données d'entrée. Maintenant, nous allons augmenter le sac à dos de capacité de 4, en gardant le reste de l'entrée. Notre contribution n'a progressé que d'un bit, mais la complexité de calcul a doublé. Si nous augmentons la capacité de 1024, nous aurions juste 10 bits de l'entrée de W au lieu de 2, mais la complexité a augmenté par un facteur de 512. Le temps de la complexité croît de façon exponentielle dans la taille de W en binaire (ou virgule) de la représentation.

Un autre exemple simple qui m'a aidé à comprendre la pseudo-polynomial concept est naïf de primalité algorithme de dépistage. Pour un nombre donné n nous allons vérifier si il est réparti de manière uniforme par chaque nombre entier dans la plage de 2..√n, alors l'algorithme prend √(n−1) étapes. Mais ici, n est l'ampleur de l'entrée, pas de sa taille.

                     Now The regular O(n) case

En revanche, à la recherche d'un tableau, pour un élément donné s'exécute en temps polynomial: O(n). Il faut au plus n étapes et ici, n est la taille de l'entrée (la longueur du tableau).

[ voir ici ]

Le calcul de bits requis pour stocker des nombres décimaux

Answer 4

Si le moteur d'exécution est plus exactement dit à O(N. 2^{bits en W}), qui est exponentielle.

Cela signifie donc que de la même façon, nous pouvons également dire-

Le moteur d'exécution est avec plus de précision O(N^{bits N}.W), qui est exponentielle.

Est ce que le droit?