如果一個NP在多項式時間內求解，可滿足性在多項式時間內求解

基於下面的鏈接，我可以知道在多項式時間求解可滿足性（NP Complete）意味着任何其他NP問題都可以在多項式時間內求解。但副 - 真的？另外，如果有任何其他NP-Complete問題的多項式是否意味着，所有其他NP-Complete都可以用多項式時間求解？如果一個NP在多項式時間內求解，可滿足性在多項式時間內求解

What are the differences between NP, NP-Complete and NP-Hard?

來源

2015-04-28 user10000000

細說你的意思，反之亦然什麼。 – orlp

所有NP完全問題是等價的，如果它們中的任何一個在多項式時間內都可解，則NP中的所有問題都可以用多項式時間求解。但是，這個問題真的是堆棧溢出的主題。更好的問問http://cs.stackexchange.com/ –

在NP完全的「完整的」意味着，如果一個問題，就是在NP完全，對於問題的解決方案給出了在NP與轉換處理的多項式量解決任何問題。

通俗地說 - 如果你解決在多項式時間內一個單一的NP完全問題，你已經證明了NP = P。

來源

2015-04-28 04:32:01 orlp

是的，但是如果一個NP在多項式時間內求解，是否意味着在多項式時間內解決所有NP完全問題。 – user10000000

@ user10000000 No. – orlp

否。考慮例如電路評估問題（對P完成）。電路評估問題提出了「這個輸入是否滿足該布爾電路」的問題。電路評估問題顯然在NP中，幷包含一個多項式解決方案。但是，這並不意味着SAT電路具有多項式時間解決方案。如果考慮另一個NP完全問題，例如哈密頓路徑問題，並且證明這個問題有多項式時間解，那麼Satisfiability也有一個多時間解決方案。 –

如果一個NP在多項式時間內求解，可滿足性在多項式時間內求解

回答

相關問題