L'argomento nel dimostrare che la funzione non è il momento polinomiale nella lunghezza del bit di ingresso sembra difettoso

Question

Attualmente sto risolvendo una domanda che chiede quale delle seguenti funzioni può essere calcolata in tempo polinomiale:

$$ n !, \ binom {n} {5}, \ binom {2n} {n}, n ^ {\ lfloor \ lg n \ rfloor}, \ lgloor\ sqrt {n} \ rfloor, \ text {il più piccolo fattore primo di} n, \ testo {il numero di fattori precedenti inferiori a} n. $$

Nel dimostrare il primo, pensai $ n!\ GeQ N $ e la dimensione di ingresso è $ \ log_2 n $ quindi l'output non può nemmeno essere scritto in tempo polinomiale.Quindi, chiaramente il calcolo non può essere fatto in tempo polinomiale.

Ma poi pensavo di dover avere qualche fraintendimento, poiché da quella logica semplicemente calcolando $ N $ dall'ingresso (cioè la funzione di identità) non dovrebbeessere tempo polinomiale.Ma questo è chiaramente possibile.

Qual è il problema nel mio pensiero, e invece come dovrei pensare a questi?

Answer 1

Dovresti misurare la lunghezza dell'output nello stesso modo in cui misurare la lunghezza dell'input.

Ad esempio, quando si calcola la funzione di identità $ f (m)= m $ , un ingresso $ m $ ha una lunghezza di ingresso $ n=theta (\ log m) $ e lunghezza dell'output anche $ N $ , che è polinomiale in $ N $ .

La funzione fattoriale, al contrario, ha una lunghezza di uscita molto lunga.Infatti, se l'input è $ N $ , quindi dalla formula di Stirling, la lunghezza dell'output è $ \ theta (n\ log n) $ , che è esponenziale nella lunghezza di ingresso $ \ theta (\ log n) $ .