algorithm - NP 问题是否一定是决策问题？

Question

斯坦福大学 Tim Roughgarden 教授在教授 MOOC表示 NP 类问题的解的长度必须是多项式。但是 wikipedia article说 NP 问题是决策问题。那么什么类型的问题基本上属于 NP 类？并且不必说此类问题的解决方案具有多项式长度输出(因为决策问题必然输出 0 或 1)？

Answer 1

他可能在谈论证人和验证者。

对于 NP 中的每个问题，都有一个验证器——读取算法/图灵机——可以在多项式时间内验证"is"的声明。

想法是，在时间限制的情况下，您有某种信息(证人)可以帮助您做到这一点。

例如，在旅行商问题中:

TSP = {(G, k) if G has a hamiltonian cycle of cost <= k}

对于给定的输入(G, k)，你只需要判断问题实例是否在TSP中。这是一个是/否的答案。

现在，如果有人过来说:这个问题实例在 TSP 中，您将需要一个证明。然后另一个人可能会给你一系列城市。然后，您可以简单地检查该顺序中的城市是否形成哈密顿循环以及该循环的总成本是否≤ k。

您可以在多项式时间内执行此过程 - 假设见证的长度是多项式。

使用这个城市序列，您因此能够正确确定问题实例确实在 TSP 中。

这就是验证者的想法:他们采用长度为多项式的证明对象/见证来检查多项式时间，即某个问题实例在语言中。