El argumento al probar que la función no es el tiempo polinomial en la longitud del bit de la entrada parece defectuosa

Question

Actualmente estoy resolviendo una pregunta que pregunta cuál de las siguientes funciones se puede calcular en el tiempo polinomial:

$$ n !, \ binom {n} {5}, \ binom {2n} {n}, n ^ {\ lfloor \ lg n \ rfloor}, \ lfloor\ sqrt {n} \ rfloor, \ texto {el factor primordial más pequeño de} N, \ texto {el número de factores primos menos que} n. $$

Al probar el primero, pensé $ n!\ GEQ N $ y el tamaño de entrada es $ \ log_2 n $ para que la salida ni siquiera se pueda escribir en el tiempo polinomial.Entonces, entonces, claramente el cálculo no se puede hacer en el tiempo polinomial.

Pero, entonces pensé que debía tener algún malentendido, ya que a esa lógica, incluso solo calculando $ n $ de la entrada (es decir, la función de identidad) no deberíaser tiempo polinomial.Pero eso claramente no es posible.

¿Cuál es el problema en mi pensamiento, y en su lugar, ¿cómo debo estar pensando en estos?

Answer 1

Debe medir la longitud de la salida de la misma manera que mide la longitud de la entrada.

Por ejemplo, al calcular la función de identidad $ f (m)= m $ , una entrada $ m $ tiene la longitud de entrada $ n=theTa (\ log m) $ y la longitud de salida también $ n $ , que es polinomial en $ n $ .

La función factorial, en contraste, tiene una longitud de salida demasiado larga.De hecho, si la entrada es $ n $ , luego por la fórmula de Stirling, la longitud de la salida es $ \ theTa (n\ log n) $ , que es exponencial en la longitud de entrada $ \ theTa (\ log n) $ .