入力のビット長の多項式時間ではないことを証明する議論は不良です

Question

現在、次の機能のどれが多項式時間で計算できるかを要求している質問を解決しています：

$$ n！、\ binom {n} {5}、\ binom {2n} {n}、n ^ {\ lfloor \ lg n \ rfrooor}、\ lforoor\ sqrt {n} \ rfloor、\ text {の最小の要素} n、\ text {より小さいプライムファクタ数} $$

最初のものを証明する $ nだと思いました！\ geq n $ と入力サイズは $ \ log_2 n $ ですので、出力は多項式時に書き込まれません。それでは、明らかに計算は多項式時間では行うことはできません。

しかし、入力から $ n $ を計算するだけでも、誤解されていると思いました（つまり、ID関数）。多項式の時間です。しかしそれは明らかに不可能です。

私の考えの問題は何ですか、そして代わりに私はこれらについてどのように考えているべきですか？

Answer 1

入力の長さを測定するのと同じ方法で出力の長さを測定する必要があります。

例えば、ID関数 $ f（m）= m $ を計算するときは、入力 $ m $ 入力長 $ n=theta（\ log m）$ および出力長さも $ n $ は、 $ n $ の多項式です。

階乗関数は、長すぎる出力長さがはるかに長すぎます。実際、入力が $ n $ の場合、スターリングの式によって、出力の長さは $ \ theta（n\ log n）$ 。入力長 $ \ theta（\ log n）$ 。