À propos de la complexité pseudo polynomiale du problème KnapSack 0/1
J'ai lu Pourquoi l'algorithme de programmation dynamique du problème du sac à dos n'est-il pas polynomial? et d'autres questions connexes, il ne s'agit donc pas d'un doublon, mais simplement d'une paire de questions connexes pour dissiper certains doutes.
Une question qui se pose fréquemment lors de la discussion de la complexité de la solution de programmation dynamique pour le problème KS est quelque chose comme ¿Pourquoi$O(n \cdot W)$n'est pas considéré comme polynomial? .
La réponse commune est que, par définition, nous nous intéressons au temps d'exécution d'un algorithme en fonction de la taille de l'entrée . Ainsi, alors qu'il est correct de dire que le temps d'exécution est limité par un polynôme dans la valeur de$W$, n'est pas polynomiale de la taille de$W$, car en fait ce que nous avons est $O(n \cdot 2^W)$.
Ici, nous pouvons également demander: Pourquoi pas$O(2^n \cdot 2^W)$? , ie par le même raisonnement$n$doit également être exponentielle dans la longueur de l'entrée. Mais le "truc" est qu'il semble$n$n'est généralement (toujours?) pas considéré comme faisant partie de l'entrée. Au lieu de cela, l'entrée est (par convention je suppose) juste une liste de$n$ poids, une liste de $n$ valeurs et capacité $W$. En effet, nous n'avons pas besoin$n$ lui-même dans l'entrée.
Des questions:
- Supposons que nous ayons $n$lui-même dans l'entrée, car rien ne m'empêche de le faire de cette manière. L'algorithme boucle de$0$ à $n$ de la même manière qu'il boucle de $0$ à $W$. Maintenant, il est correct de dire que le temps de fonctionnement est$O(2^n \cdot 2^W)$ ?.
- Mais si (1) est le bon, je ne pense pas que cet algorithme avec $n$dans l'entrée ont le même comportement asymptotique que le commun. Comment$O(2^n \cdot 2^W)=O(2^{n+W})$ comparer avec $O(n \cdot 2^W)$ ?.
- Considérons l'algorithme récursif naïf habituel pour le problème KS 0/1. On dit que c'est$O(2^n)$, car dans le pire des cas, deux appels récursifs sur $n-1$sont nécessaires. Dans ce cas,$n$ est clairement dans l'entrée, mais nous considérons $n$comme valeur lors de l'analyse de récurrence. Donc, compte tenu de la discussion précédente, je suis tenté de dire qu'en fait nous avons$O(2^{(2^n)})$ qui est double exponentielle et pas seulement exponentielle ... mais cela a-t-il un sens?
Réponses
Qu'il s'agisse $n$est "inclus dans l'entrée" ou non n'est pas pertinent. Aucune "astuce" n'est utilisée pour se cacher sournoisement$n$ à partir de l'entrée en l'incluant implicitement comme longueur d'une liste.
L'entrée est au moins $n$bits de long car il doit inclure une liste de toutes les valeurs et poids des éléments. Si les valeurs et les poids des éléments ne nous sont pas communiqués dans le cadre de l'entrée, comment sommes-nous censés résoudre le problème (si nous ne connaissons pas le poids / la valeur de certains éléments)?
Maintenant, puisque nous savons que l'entrée a une longueur (en bits) au moins $n$, à tout moment d'exécution du formulaire $n, n^2, n^3,...$est polynomial dans la longueur de l'entrée .
Cependant, la longueur d'une (représentation raisonnable de l'entrée) est au plus $O(n\log W)$(en supposant que les valeurs des éléments sont du même ordre de grandeur que leurs poids). Pour chaque article, nous devons donner le poids et la valeur, et cela peut être fait avec$\log W$ bits par article (en donnant la représentation binaire du poids / valeur).
Comme l'a noté Yuval, $nW$ n'est pas polynomial dans $n\log W$.
Peu importe si nous considérons l'entrée comme les listes uniquement ou les listes "avec" $n$. Si nous incluons également$n$ explicitement, il fait juste l'entrée $\log n$bits plus longs . Mais puisque l'entrée est déjà au moins$n$ bits de long, ayant $\log n$ les bits supplémentaires ne font aucune différence.
Supposons qu'il y ait $n$ poids entiers de grandeur au plus $W$. Nous pouvons encoder chaque poids en$O(\log W)$ bits, et donc la longueur totale d'entrée (en bits) est $O(n\log W)$. Un algorithme est polynomial si son temps d'exécution est$O((n\log W)^C)$ pour certains $C$. La programmation dynamique s'exécute dans$\Theta(nW)$. Malheureusement,$nW$ ne peut pas être limité par $O((n\log W)^C)$ pour toute constante $C$.