NP类:为什么输出多项式长度？

Question

对于符合NP类条件的问题：

1. 这个问题的解必须有一个多项式输出长度，并且
2. 解必须在多项式时间内可验证。

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

PS :我认为多项式输出长度是在多项式时间内输出可验证的必要条件。(但只要说可以在多项式时间内验证解就足够了。)

Answer 1

多项式长度施加是因为你是建模的机器作为一个通用图灵机。

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

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