algorithm - NP类：为什么多项式长度输出？

Question

对于有资格获得 NP 类的问题：

1. 该问题的解决方案必须具有多项式输出长度，并且
2. 解决方案必须在多项式时间内是可验证的。

多项式输出长度的意义是什么？

PS：我认为多项式输出长度是输出在多项式时间内可验证的必要先决条件。（但是仅仅说可以在多项式时间内验证解决方案仍然是足够的。）

Answer 1

多项式长度强制是因为您将机器建模为通用图灵机。

在这种情况下，输出“磁带”必须是多项式长度。

这不是因为您使用的是现代语言并期望得到多项式长度的结果。