斯坦福大学的 Tim Roughgarden 教授在教授MOOC时说，NP 类问题的解决方案必须是多项式长度。但是维基百科的文章说 NP 问题是决策问题。那么什么类型的问题基本上属于 NP 类？并且没有必要说此类问题的解决方案具有多项式长度输出（因为决策问题必须输出 0 或 1）？
问问题
1024 次
3 回答
4
他可能在谈论证人和核实人。
对于 NP 中的每个问题，都有一个验证器——读取算法/图灵机——可以在多项式时间内验证“是”声明。
这个想法是，在时间有限的情况下，你有某种信息——证人——来帮助你做到这一点。
例如，在旅行商问题中：
TSP = {(G, k) if G has a hamiltonian cycle of cost <= k}
对于给定的输入(G, k)，您只需要确定问题实例是否在TSP中。这是一个是/否的答案。
现在，如果有人过来说：这个问题实例在TSP中，你会要求证明。然后另一个人可能会给你一系列城市。然后，您可以简单地检查该顺序中的城市是否形成哈密顿循环以及循环的总成本是否≤ k。
您可以在多项式时间内执行此过程——假设见证的长度是多项式的。
使用此城市序列，您因此能够正确确定问题实例确实在TSP中。
这就是验证者的想法：他们采用长度为多项式的证明对象/见证来检查多项式时间，即某个问题实例在语言中。
于 2013-02-10T17:18:21.783 回答
2
NP的标准定义是它只是一类决策问题。决策问题总是产生是/否的答案，因此具有恒定大小的输出。
于 2013-02-10T15:41:44.550 回答
1
s没有观看视频/课程，但我猜他在谈论证书/验证而不是解决方案。巨大差距。
于 2013-02-10T16:18:36.580 回答