PSedu-polynomial Temps: conflit avec la définition de la taille de l'entrée

Question

De Wikipédia

Dans la théorie de la complexité de calcul, un algorithme numérique se déroule dans pseudo-polynomial temps si son temps d'exécution est un polynôme dans la longueur de l'entrée (le nombre de bits requis pour le représenter) et la valeur numérique de l'entrée (le plus grand entier présent dans l'entrée). En général, la valeur numérique de l'entrée est exponentielle dans la longueur d'entrée, c'est pourquoi un pseudo-polynomial L'algorithme de temps ne s'exécute pas nécessairement en temps polynomial par rapport à la longueur d'entrée.

De cette SO POST c'était très utile.

Un algorithme s'exécute pseudo-polynomial temps si le temps d'exécution est un polynôme dans la valeur numérique de l'entrée, plutôt que dans le nombre de bits requis pour le représenter.

Et ça Conférence du MIT OCW Sur le sac à dos de Knapsack DP et la définition du temps pseudo-polynomial.

Ils parlent tous de la même chose en ce sens qu'un temps d'exécution est le pseudo-polynomial lorsqu'il s'agit d'un polynôme multivarié de $ (x, k) $ où $ x $ dénote la taille de l'entrée et $ k $ est un entier (numérique valeur) impliquée. Étant donné que $ k $ est souvent exponentiel dans $ x $, le temps pseudo-polynomial n'est pas nécessairement le temps polynomial en $ x $, le nombre de bits nécessaires pour représenter l'entrée. Mathématiquement, $ k = theta (2 ^ {x}) $, 2 est remplaçable par une constante.

Cela fonctionne très bien lorsque nous avons une valeur numérique $ k $ comme entrée avec le temps d'exécution $ theta (k) $. Alors $ x = theta ( log k) $ et nous avons du temps d'exécution $ theta (2 ^ {x}) $. Tout est propre.

Et puis je commence à voir des problèmes plus compliqués dans d'autres algorithmes. Par exemple, dans le cas de sac à dos, Soit $ n $ le nombre de choses ou d'objets dans l'entrée. Comme décrit dans le Vidéo du MIT, l'entrée est $ x = theta (nlogs) $ et le temps d'exécution est $ theta (ns) $. L'instructeur décrit que puisque $ s $ est exponentielle dans le taille d'entrée $ log s $ (le nombre de bits nécessaires pour représenter la valeur numérique), nous pouvons voir comment le temps d'exécution du sac à dos n'est pas le temps polynomial. $ log s $ n'est qu'une partie de $ x $, donc je ne vois pas comment $ theta (n cdot 2 ^ { log s}) $ est exponentiel dans $ theta (n log s) $ . Comment le temps d'exécution est-il exprimé sous la forme $ o (c ^ {x}) $ où $ c $ est une constante?

Quelque chose de similaire se produit pour compter le temps de fonctionnement. La SO POST donne du temps d'exécution $ o (n + k) $. Il donne la même logique que ci-dessus pour dire que le temps d'exécution est exponentiel dans la taille d'entrée $ log K $. Mais pour moi, il semble que $ x = theta (n log k) $ puisque l'entrée est une liste de $ n $ avec la valeur maximale $ k $. Je ne vois pas vraiment comment $ o (n + k) $ peut être exponentiel dans $ x $ juste parce que $ k $ est exponentiel dans le nombre de bits nécessaires pour le représenter, car $ log k $ n'est certainement pas $ x x $, seulement une partie de celui-ci. Même chose: le temps d'exécution ne semble pas exponentiel dans $ x $, plutôt que dans $ log s $.

Donc, soit je n'obtiens toujours pas ce que signifie avoir exponentiel "longueur de l'entrée" est ou il y a un conflit avec la façon dont les gens définissent longueur de l'entrée. La vidéo du MIT définit la taille des entrées similaire à la façon dont je pense à $ x $ tandis que de nombreuses autres sources ont une opinion différente semble-t-il. Je le vois comme le Nombre total de bits nécessaires pour représenter l'ensemble de l'entrée, mais une analyse le voit simplement comme le nombre de bits nécessaires pour représenter une valeur numérique qui n'est qu'une partie de l'ensemble de l'entrée. Le temps d'exécution est-il exponentiel dans la taille de l'entrée s'il est exponentiel dans la taille d'une partie de l'entrée ou du tout ?? Précisez s'il vous plaît!!