证明该功能不是多项式的输入似乎有缺陷的多项式时间

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 $ ，那么通过斯特林的公式，输出的长度是 $ \ theta（n\ log n）$ ，它是输入长度的指数 $ \ theta（\ log n）$ 。