代码之家 › 专栏 › 技术社区 › Jason Baker

如果P=NP,NP中间产物能存在吗?

np-complete complexity-theory

3

Jason Baker · 技术社区 · 16 年前

我的理解是,拉德纳定理基本上是这样的:

P!=NP意味着存在一组NPI,其中NPI不在P和P中 NPI不是NP完全的

如果我们假设P=NP而不是P!=NP我们知道如果NP中间体不存在,那么P=NP。但是如果P=NP,NP中间产物能存在吗?

4 回复 | 直到 16 年前

1

3

Michael Madsen 16 年前

NPI必须暗示它在NP中,但它不是NP完全的。

如果P=NP,那么P和NP中的所有问题都将是NP完全的,因为任何问题在多项式时间内都可以化简为另一个问题(并且*不能是NP完全的,因为我们不能将任意问题映射到它们中的任何一个-对于正/负的情况,我们将没有任何东西可以映射到。但是,因为它们在P中,所以我们不关心它们

由于NP中的所有问题都是NP完全问题,NPI不可能存在。

2

3

sepp2k 16 年前

你错过了NPI的一个属性:NPI的每个元素都在NP中(但不是在P中)。如果P=NP,这显然是不可能的,所以如果P=NP,NPI必须是空的。

3

2

Michael Ekstrand 16 年前

4

1

user13675 12 年前

从基本逻辑来看,$A\rightarrow B$没有说明$not(A)$的任何内容。。。很不幸。

此外,如果$P=NP$,并且$NP$可约为$NP完全$。。。那就意味着我们在计算中计算的大多数问题(加法、傅立叶变换、排序)都可以简化为,比如说,子集和。。。。假设库克定理成立。这会让人心神不宁。