我的理解是，拉德纳定理基本上是这样的：
P != NP 意味着存在一个集合 NPI，其中 NPI 不在 P 中并且 NPI 不是 NP 完全的
如果我们假设 P = NP 而不是 P != NP，这个定理会发生什么？我们知道如果 NP Intermediate 不存在，那么 P = NP。但是如果 P = NP，NP Intermediate 是否存在？
问问题
1195 次
4 回答
4
NPI 必须暗示它在 NP 中，但它不是 NP 完全的。
如果 P = NP，那么 P 和 NP 中的所有问题都是 NP 完全的，因为任何问题都可以在多项式时间内简化为另一个问题（∅ 和 Σ* 不能是 NP 完全的，因为我们不能映射任意问题到他们中的任何一个 - 我们将没有任何东西可以映射到正面/负面情况。但是，由于它们在 P 中，因此出于这个问题的目的，我们不关心它们。）
由于 NP 中的所有问题都是 NP 完全的，因此 NPI 不存在。
于 2010-04-11T21:52:27.377 回答
3
您错过了 NPI 的一个属性：NPI 的每个元素都在 NP 中（但不在 P 中）。如果 P=NP，这显然是不可能的，所以如果 P=NP，NPI 必须为空。
于 2010-04-11T21:51:39.880 回答
2
如果 P=NP，则假设 NPI 是 NP 的子集，则 NPI 不存在，因为所有 NP 都在 P 中，因此 NPI 定义的“不在 P”部分不会存在任何问题。因此，在这种情况下，类 NPI 将为空。
于 2010-04-11T21:52:11.527 回答
1
Ladner 定理在其经典公式中没有说明 P=NP 的情况。
从基本逻辑来看，$A\rightarrow B$ 没有说明任何关于 $not(A)$... 的信息。
此外，如果 $P=NP$ 并且 $NP$ 是 Cook-reducible 到 $NP-complete$... 那么这意味着我们在计算中计算的大多数问题（加法、傅里叶变换、排序）都可以简化为，比如说, 子集总和.... 假设库克定理是有效的。这将是相当令人费解的。
但是根据拉德纳定理，我们可以对 $P=NP$ 的情况说任何话。
于 2014-05-03T16:37:46.807 回答