certificate - 复杂等级中的证书长度

Question

试图决定一种语言的成员资格的非确定性机器会被呈现一个提示（称为“见证”或“证书”），该提示（称为“见证”或“证书”）可以证明成员（没有为语言之外的元素提供这样的见证；定义是不对称的）。

那么，如果一个非确定性算法可以在 O(f(n)) 时间内解决问题，这是否意味着证书的长度为 f(n)？输入大小为n？

此外，如果存在可以在 O(f(n)) 时间内验证证书的算法 A，这如何意味着存在可以在 O(f(n)) 时间内解决问题的非确定性算法？

Answer 1

恕我直言：

• 那么，如果一个非确定性算法可以在 O(f(n)) 时间内解决问题，这是否意味着证书的长度为 f(n)？

不

• 输入大小为n？

是的

• 此外，如果存在可以在 O(f(n)) 时间内验证证书的算法 A，这如何意味着存在可以在 O(f(n)) 时间内解决问题的非确定性算法？

这里没有暗示。声明是，如果非确定性算法可以在 O(f(n)) 中解决问题，并且可以在 O(g(n)) 中验证解决方案（如果需要，可以使用证书或白度），并且 f 和 g 是多项式, 比问题是 NP 难。（不一定是 NP 完全的）