NP完全減少

我對於與NP完全問題有關的減少有這個困惑。假設我們有兩個問題R和S不知道在NP中。現在如果我們有一個衆所周知的NP完全問題的多項式時間減少到R，並且我們也有一個從S到NP完全問題的多項式時間減少。對於R和S問題可以說什麼呢？它們是NP完成的還是NP很難？NP完全減少

我投票結束這個問題作爲題外話，因爲這不是關於編程，而是數學。 –

如果一個NP完全問題在多項式時間內減少到R，那麼NP中的所有問題都是這樣的;因此，R是NP-Hard。

如果S簡化爲一個NP完全問題，則S是NP。

兩者都不一定是NP完全;我們不知道R是否是NP（也許它是不可判定的），或者S是否是NP-Hard（也許它是微不足道的？）。

2013-02-05 20:35:13 Patrick87

謝謝你，我有我的心中另一個疑問讓我們說一個問題L在NP是減少到一個問題L'..然後可以說什麼問題L' – user2044593

@ user2044593沒有任何實質：L'可能NP-Complete，NP，但不是NP-Complete（假設P！= NP）或P。請注意，任何問題都會自行消除。即使你拋出這個微不足道的情況，也不難發現問題L'，這樣L'和L就可以通過基本相同的算法解決。 – Patrick87

感謝您的澄清！ – user2044593

回答