complexity-theory - 为什么 NP 只是一组决策问题？

Question

摘自维基百科，但我看到的所有定义都与此类似:

"NP is the set of decision problems where the "yes"-instances can be accepted in polynomial time by a non-deterministic Turing machine."

为什么 NP 仅限于决策问题？是吗？

以子集和为例:

(类型 1)决策问题 - 是否存在总和为 k 的 A 的子集 B？

(类型 2)“正常”问题 - 总和为 k 的 A 的子集 B 是什么？

我在类型 2 上写了“正常”，因为这感觉就像解决此类问题时通常所做的那样。

我是否正确理解，使用 NP 的定义，类型 1 属于 NP 而类型 2 不属于？

感觉这个定义在有时非正式地写的方式上同样有效

"All problems whose solutions can be checked in polynomial time".

(我发现了一个类似的问题，但它似乎并没有真正回答这个问题)

Answer 1

你是对的，NP 是一类决策问题(回答是或否的问题)，所以问题 (1) 在 NP 中，问题 (2 ) 不在 NP 中。以这种方式设置 NP 的部分原因是历史原因(形式语言理论关注字符串/自然数是否属于特定集合的问题)，部分原因是为了数学上的简单性(因为这些问题只有是/否的答案，你可以将问题作为"is"实例的集合来讨论，并对这些集合执行集合论操作，其中一部分是使某些定义更容易使用(可还原性，例如，从语言的角度来说真的很容易表达)。

这并不是说更一般的问题不有趣——它们绝对有趣!您所描述的类型 (2) 的问题可能不在 NP 中，但它是在称为 FNP 的复杂类中(函数NP)，这是 NP 的自然泛化，适用于寻找满足可在多项式时间内检查的标准的特定对象的情况。还有一个对应版本的 P 类称为 FP，并且有一个对应的 FP 与 FNP 问题。 p>