如果P = NP，是否存在NP中間體？

P = NP意味着存在一組NPI其中NPI是不是在P和 NPI是不是NP完全

什麼如果我們假設P = NP而不是P！= NP，那麼碰巧這個定理？我們知道如果NP Intermediate不存在，那麼P = NP。但如果P = NP，NP中性是否存在？

2010-04-11 Jason Baker

NPI必須暗示它在NP中，但它不是NP完全的。

如果P = NP，那麼P和NP中的所有問題都將是NP完全的，因爲在多項式時間內任何問題都可以歸約到另一個問題上（∅和Σ*不能是NP完全的，因爲我們不能將一個任意的問題映射到其中任何一個 - 我們將沒有任何東西可以映射到正面/負面的情況，但是，因爲它們在P中，所以我們不關心這個問題。）

由於NP中的所有問題都是NP完全的，所以NPI不能存在。

來源

2010-04-11 21:52:27

所以出於好奇，爲什麼Ladner定理會使用「if」而不是「if if only」？ – 2010-04-12 01:03:59

@Jason：這是一個很好的問題。考慮到爲任何NP問題構造一個映射約化是相當容易的，例如它運行在多項式時間內（假設P = NP），也許他認爲相反的情況太微不足道了。當然，這也可能只是一種疏忽，當他提出他的定理時他沒有考慮這個問題。 – 2010-04-12 07:21:10

@Jason：因爲另一個方向是微不足道的。請參閱第1段：http://en.wikipedia.org/wiki/NP-intermediate – 2011-08-10 12:45:22

您錯過了NPI的一個屬性：NPI的每個元素都在NP中（但不在P中）。如果P = NP，這顯然是不可能的，所以如果P = NP，則NPI必須是空的。

來源

2010-04-11 21:51:39 sepp2k

如果P = NP，那麼NPI就不能存在，因爲它是NP的一個子集，因爲所有NP都在P中，因此NPI定義中的「不在P」部分不會產生任何問題。所以在這種情況下，NPI類將是空的。

來源

2010-04-11 21:52:11

Ladner定理在其經典公式中並沒有說明P = NP的情況。從基本邏輯來看，$ A \ rightarrow B $沒有說明有關$ not（A）$ ...的任何內容。不幸的是，另外，如果$ P = NP $和$ NP $可以簡化爲$ NP-complete $ ...，那麼這就意味着我們在計算（加法，傅里葉變換，排序）中計算的大多數問題都是可以簡化爲子集和......假設庫克定理是有效的。這將是相當令人費解的。

但是，根據Ladner定理，我們可以對任何有關情況$ P = NP $進行說明。

來源

2014-05-03 16:37:46 user13675

如果P = NP，是否存在NP中間體？

回答

相關問題