为什么 NP 只是一组决策问题？
Why is NP only a set of decision problems?
摘自维基百科，但我看到的所有定义都与此类似：
"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".
（我发现了一个类似的问题，但它似乎并没有真正回答这个问题）
你是对的，NP 是一个 class 的决策问题（回答是或否的问题），所以问题 (1) 在 NP，问题（2）不在NP中。以这种方式设置 NP 的部分原因是历史原因（形式语言理论关注 strings/natural 数字是否属于特定集合的问题），部分原因是为了数学上的简单性（因为这些问题只有 yes/no 个答案，你可以把一个问题当作 "yes" 个实例的集合来讨论，并对这些集合执行集合论操作），其中一部分是使某些定义更容易使用（例如，从语言的角度来看，可还原性真的很容易表达）。
这并不是说更一般的问题不有趣——它们绝对有趣！您所描述的类型 (2) 的问题可能不在 NP 中，但它 是 的复杂度 class FNP（函数NP），这是NP对作业是找到满足可以在多项式时间内检查的标准的特定对象。 classP还有对应的版本叫做FP，还有对应的FP与 FNP 问题相比。
什么是 P=NP 的简短解释：
- P[多项式时间]是或否题如果答案可以
以多项式时间计算。
- 一个 yes-or-no 问题在 NP [Non-deterministic 多项式时间] 如果一个
是的答案可以在多项式时间内验证。
您可以在我的短文中阅读更多关于 P=NP 的内容：https://medium.com/@officialgupta/what-is-p-np-2b0fd7b9bd83
摘自维基百科，但我看到的所有定义都与此类似：
"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".
（我发现了一个类似的问题，但它似乎并没有真正回答这个问题）
你是对的，NP 是一个 class 的决策问题（回答是或否的问题），所以问题 (1) 在 NP，问题（2）不在NP中。以这种方式设置 NP 的部分原因是历史原因（形式语言理论关注 strings/natural 数字是否属于特定集合的问题），部分原因是为了数学上的简单性（因为这些问题只有 yes/no 个答案，你可以把一个问题当作 "yes" 个实例的集合来讨论，并对这些集合执行集合论操作），其中一部分是使某些定义更容易使用（例如，从语言的角度来看，可还原性真的很容易表达）。
这并不是说更一般的问题不有趣——它们绝对有趣！您所描述的类型 (2) 的问题可能不在 NP 中，但它 是 的复杂度 class FNP（函数NP），这是NP对作业是找到满足可以在多项式时间内检查的标准的特定对象。 classP还有对应的版本叫做FP，还有对应的FP与 FNP 问题相比。
什么是 P=NP 的简短解释：
- P[多项式时间]是或否题如果答案可以 以多项式时间计算。
- 一个 yes-or-no 问题在 NP [Non-deterministic 多项式时间] 如果一个 是的答案可以在多项式时间内验证。
您可以在我的短文中阅读更多关于 P=NP 的内容：https://medium.com/@officialgupta/what-is-p-np-2b0fd7b9bd83