什么是 NP 中级问题？
What are NP-Intermediate problems?
假设 P != NP
欧拉图显示了不属于P和NP-complete的部分。我在维基百科上看到这个集合叫做 NP-Intermediate。
我对如何定义 NPI 问题有一些疑问？
NP-中级问题是
的决策问题
- 在NP（即"yes"答案可以多项式时间验证），
- 不在P中（即没有多项式时间算法求解），而
- 不是 NP-完整的。
最后一个标准可以用多种不同的方式来表述。一种说法是，从 SAT 到那个特定问题没有多项式时间映射缩减。
这些问题目前主要是理论上的兴趣，因为我们不知道是否存在任何 NP-中间问题 - 如果我们能找到一个，我们就会遇到问题在 NP 中不在 P 中，这意味着 P ≠ NP！然而，它们很有趣，因为如果我们可以证明 P ≠ NP，那么我们就知道 中存在一些问题NP 太难在多项式时间内解决，但不在 NP 中的难题 "hardest" 中（这些问题是NP-完成）。
如果P = NP，那么就不会有任何NP -中间问题，因为您在 NP 中不会遇到问题，但在 P 中不会遇到问题。如果 P ≠ NP，那么拉德纳定理保证至少存在一个 NP-中间问题，但是确实因此，通过专门构建一个高度人为的问题，并且在这种情况下仅设计为 NP-中间。现在，除了少数例外（特别是 graph isomorphism problem），我们在 NP 中知道的所有问题都直接在 P 中或已知为 NP-完整。
假设 P != NP
欧拉图显示了不属于P和NP-complete的部分。我在维基百科上看到这个集合叫做 NP-Intermediate。
我对如何定义 NPI 问题有一些疑问？
NP-中级问题是
的决策问题- 在NP（即"yes"答案可以多项式时间验证），
- 不在P中（即没有多项式时间算法求解），而
- 不是 NP-完整的。
最后一个标准可以用多种不同的方式来表述。一种说法是，从 SAT 到那个特定问题没有多项式时间映射缩减。
这些问题目前主要是理论上的兴趣，因为我们不知道是否存在任何 NP-中间问题 - 如果我们能找到一个，我们就会遇到问题在 NP 中不在 P 中，这意味着 P ≠ NP！然而，它们很有趣，因为如果我们可以证明 P ≠ NP，那么我们就知道 中存在一些问题NP 太难在多项式时间内解决，但不在 NP 中的难题 "hardest" 中（这些问题是NP-完成）。
如果P = NP，那么就不会有任何NP -中间问题，因为您在 NP 中不会遇到问题，但在 P 中不会遇到问题。如果 P ≠ NP，那么拉德纳定理保证至少存在一个 NP-中间问题，但是确实因此，通过专门构建一个高度人为的问题，并且在这种情况下仅设计为 NP-中间。现在，除了少数例外（特别是 graph isomorphism problem），我们在 NP 中知道的所有问题都直接在 P 中或已知为 NP-完整。