L'argument dans la preuve de cette fonction n'est pas une durée polynomiale dans une longueur de bits d'entrée semble défectueuse

Question

Je résolvez actuellement une question qui demande laquelle des fonctions suivantes peut être calculée en polynôme Time:

$$ n !, \ binom {n} {5}, \ binom {2n} {n}, n ^ {\ lfloor \ lg n \ rfloor}, \ lflfloor\ sqrt {n} \ rfloor, \ texte {le plus petit facteur prime de} n, \ Text {Le nombre de facteurs primaires inférieurs à} n. $$

En prouvant le premier, je pensais N $ N!\ geq n $ et la taille d'entrée est $ \ log_2 n $ de sorte que la sortie ne peut même pas être écrite en temps polynomial.Donc, alors clairement, le calcul ne peut pas être fait en temps polynomial.

Mais puis je pensais que je dois avoir un malentendu, car par cette logique, même calculer simplement $ n $ de l'entrée (c'est-à-dire la fonction d'identité) ne doit pasêtre du temps polynomial.Mais ce n'est clairement pas possible.

Quel est le problème dans ma pensée, et plutôt comment devrais-je penser à ceux-ci?

Answer 1

Vous devez mesurer la longueur de la sortie de la même manière que vous mesurez la longueur de l'entrée.

Par exemple, lors du calcul de la fonction d'identité $ f (m)= M $ , une entrée $ m $ a une longueur d'entrée $ n=theta (\ journal m) $ et la longueur de sortie également $ n $ , qui est polynôme dans $ n $ .

La fonction factorielle, en revanche, a beaucoup trop longueur de sortie.En effet, si l'entrée est $ n $ , puis par la formule de Stirling, la longueur de la sortie est $ \ theta (n\ journal n) $ , qui est exponentiel dans la longueur d'entrée $ \ theta (\ journal n) $

.

.