如果 P = NP，NP-Intermediate 是否存在？
我的理解是拉德纳定理基本上是这样的：
P != NP 意味着存在一个集合 NPI，其中 NPI 不在 P 中并且 NPI 不是 NP 完全的
如果我们假设 P = NP 而不是 P != NP，这个定理会发生什么？我们知道，如果 NP Intermediate 不存在，则 P = NP。但如果P = NP，NP中间是否存在？
My understanding is that Ladner's theorem is basically this:
P != NP implies that there exists a set NPI where NPI is not in P and
NPI is not NP-complete
What happens to this theorem if we assume that P = NP rather than P != NP? We know that if NP Intermediate doesn't exist, then P = NP. But can NP Intermediate exist if P = NP?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
NPI 必须暗示它属于 NP，但它不是 NP 完全的。
如果 P = NP，则 P 和 NP 中的所有问题都将是 NP 完全的，因为任何问题都可以在多项式时间内还原为另一个问题（∅ 和 Σ* 不能是 NP 完全的，因为我们无法映射任意问题到它们中的任何一个 - 我们不会有任何东西可以映射到正/负情况，但是，由于它们在 P 中，因此我们不关心它们。）
因为 NP 中的所有问题都是 。 NP完全，NPI不可能存在。
NPI must imply that it is in NP, but that it is not NP-complete.
If P = NP, then all problems in P and NP will be NP-complete, because any problem will be reducible to another one in polynomial time (∅ and Σ* cannot be NP-complete, because we can't map an arbitrary problem to either of them - we won't have anything to map to for the positive/negative case. However, since they are in P, we don't care about them for the purpose of this question.)
Since all problems in NP are NP-complete, NPI cannot exist.
你错过了 NPI 的一个性质：NPI 的每个元素都在 NP 中（但不在 P 中）。如果 P=NP，这显然是不可能的，因此如果 P=NP，NPI 必须为空。
You missed one property of NPI: Every element of NPI is in NP (but not in P). This is clearly impossible if P=NP, so if P=NP, NPI must be empty.
如果 P=NP，则假设 NPI 是 NP 的子集，则 NPI 不能存在，因为所有 NP 都在 P 中，因此 NPI 定义的“不在 P”部分对于任何问题都不成立。因此，在这种情况下，NPI 类将为空。
If P=NP, then NPI cannot exist assuming that it is a subset of NP, as all of NP is in P and thus the "not in P" part of the definition of NPI would not hold for any problem. So the class NPI would be empty in that case.
拉德纳定理的经典表述没有说明任何有关 P=NP 的情况。
从基本逻辑来看，$A\rightarrow B$ 没有说明任何关于 $not(A)$ 的内容...不幸的是。
此外，如果 $P=NP$ 且 $NP$ 可以 Cook-reducible 为 $NP-complete$... 那么这意味着我们在计算中计算的大多数问题（加法、傅立叶变换、排序）都可以简化为，比如说，子集和....假设库克定理有效。这将是相当令人费解的。
但根据拉德纳定理，我们可以对 $P=NP$ 的情况说任何话。
Ladner's theorem in its classical formulation does not state anything about the case where P=NP.
From basic logic, $A\rightarrow B$ does not state anything about $not(A)$... unfortunately.
Furthermore, if $P=NP$ and $NP$ is Cook-reducible to $NP-complete$... then it would mean that most problems that we compute in computing (addition, Fourier Transforms, sorting) are reducible to, say, subset sum.... assuming that Cook's theorem is valid. This would be quite mind-bending.
But from Ladner's theorem, we just can say anything about the case $P=NP$.