Аргумент в доказании того, что функция не является многочленным временем в длину битов ввода, кажется неисправным

Question

Я в настоящее время решаю вопрос, который спрашивает, какая из следующих функций может быть рассчитана в многочленом времени:

$$ n !, \ binom {n} {5}, \ binom {2n} {n}, n ^ {\ lfloor \ lg n \ Rfloor}, \ lfloor\ sqrt {n} \ Rfloor, \ Text {наименьший просторный фактор} n, \ Text {количество главных факторов меньше, чем} n. $$

В доказании первого, я думал, что $ n!\ geq n $ и размер ввода - $ \ log_2 n $ поэтому вывод не может быть даже написан в многочленом времени.Таким образом, четко расчет не может быть выполнен в многочленом времени.

Но потом я думал, что у меня должно быть некоторое недоразумение, так как в этой логике даже вычисления $ n $ от входа (то есть функция идентичности) не должнабыть многочленным временем.Но это явно невозможно.

Что такое проблема в моем мышлении, а вместо этого я должен думать об этом?

Answer 1

Вы должны измерить длину выхода таким же образом, вы измеряете длину ввода.

Например, при вычислении функции идентификаторов $ f (m)= m $ , вход $ m $ имеет длину ввода $ n=theta (\ log m) $ и длина вывода Также $ n $ , который является многочлен в $ n $ .

Факториальная функция, напротив, имеет слишком длинную длинную выходную длину.Действительно, если вход - $ n $ , то по формуле STIRLING, длина выхода - $ \ Theta (n\ log n) $ , который экспоненциально на входной длине $ \ Theta (\ log n) $ .