问NP问题有必要成为决策问题吗？

EN

他可能说的是目击者和验证者。

对于NP中的每个问题，都有一个验证器-读取算法/图灵机-它可以在多项式时间内验证“是”-claims。

这个想法是，在时间有限的情况下，你有某种信息-证人-来帮助你做到这一点。

例如，在旅行推销员问题中：

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

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

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

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

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

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

NP的标准定义是它只是一类决策问题。决策问题总是产生一个是/否的答案，因此具有固定大小的输出。

我没有看视频/课程，但我猜他说的是证书/验证，而不是解决方案。差别很大。