Argumento em provar que a função não é tempo polinomial em um pouco de comprimento de entrada parece com defeito

Question

Actualmente estou resolvendo uma pergunta que solicita quais das seguintes funções podem ser calculadas no tempo polinomial:

$$ n !, \ binom {n} {5}, \ binom {2n} {n}, n ^ {\ lFloor \ lg n \ rfloor}, \ l flloor\ sqrt {n} \ rfloor, \ text {o menor fator prime de} n, \ text {o número de fatores primos menores que} n. $$

Ao provar o primeiro, eu pensei $ n!\ Geq n $ e o tamanho da entrada é $ \ log_2 n $ para que a saída não seja escrita no tempo polinomial.Então, então claramente o cálculo não pode ser feito em tempo polinomial.

Mas então eu pensei que devo ter algum mal-entendido, já que por essa lógica, mesmo apenas calculando $ n $ da entrada (isto é, a função de identidade) não deveser tempo polinomial.Mas isso claramente não é possível.

Qual é o problema no meu pensamento e, em vez disso, como devo pensar nesses?

Answer 1

Você deve medir o comprimento da saída da mesma forma que você mede o comprimento da entrada.

Por exemplo, ao calcular a função de identidade $ F (m)= M $ , uma entrada $ m $ tem comprimento de entrada $ n=theta (\ log m) $ e comprimento de saída também $ n $ , que é polinômio na $ n $ .

A função fatorial, em contraste, tem um comprimento de saída muito longo.De fato, se a entrada é $ n $ , então pela fórmula de Stirling, o comprimento da saída é $ \ theta (n\ log n) $ , que é exponencial no comprimento de entrada $ \ theta (\ log n) $ .