和这个问题有点相关。
NP 复杂性类的基于验证者的定义说：
NP是确定性图灵机验证器在多项式时间内接受的语言类别。
P中的所有问题都被认为在NP中。作为解释，通常有以下说法：
给定P中问题的证书，我们可以忽略证书并在多项式时间内解决问题。
验证者需要使用证书并证明问题可以在多项式时间内得到验证。为什么每个人都在说忽略证书并解决问题？解决问题是否等同于提供证书？
问问题
729 次
1 回答
1
在担心验证者是否“使用”证书时，您对“验证者”这个词的理解太过字面了。验证者是一种算法，它采用原始问题和一些附加信息（“证书”），并在多项式时间内提供正确答案（“是”或“否”）。我们称它为验证者，但这并不意味着它是一个新的“工作”。
对于像子集总和这样的问题，证书是一个有用的捷径——我们得到一个子集，我们只需要检查 a) 加起来为 0 并且 b) 是一个子集。但如果我们已经知道问题可以在多项式时间内解决，那么这条捷径就变得不必要了。
于 2013-06-24T19:36:30.937 回答