NP完整的定義

Question

我試圖理解NP Complete的正式定義並且有一些問題。我想知道如果有人能提供更多的見解。

Jon Kleinberg algorithms book表示如果每個NP問題都可以歸結爲問題X，那麼問題X在NP集合中。

現在既然P是NP的一個子集，那麼我們可以將P中的任何問題都簡化爲多項式時間的NP完全問題。這導致一個矛盾，即由於減少是在多項式時間內，我們可以在多項式時間內解決這個NP完全問題。這不可能是真的。所以我不確定這個推理是錯誤的。

此外，如果我們能夠在NP Complete中減少多項式時間中的任何NP問題，那麼爲什麼我們說NP Complete更難。由於縮減在多項式時間內，漸近地說，它不應該有所作爲。

Answer 1

現在既然P是NP的一個子集，那麼我們可以將P中的任何 問題簡化爲多項式時間的NP完全問題。這導致 矛盾，由於減少是在多項式時間，我們 可以在多項式時間解決這個NP完全問題。

你得到了減少錯誤的方向。如果可以將任何NP完全問題簡化爲給定的P問題，那麼P = NP，因爲這意味着這個P問題比任何NP完全問題更難或等價。 P問題可以歸結爲NP問題的事實並不表明它比NP更難 - 它表明它比NP更容易，這並不奇怪或矛盾。

假設我們可以將最短路徑減少到TSP的一次運行，並且假設TSP只能通過枚舉（指數複雜度）來解決。那麼，最短路徑是多項式，減少是多項式（O（1）），但TSP不是多項式。這是一個假設的例子。但有希望的是，它表明TSP可以一次運行解決SP的事實並不意味着TSP很容易通過任何措施。 TSP的複雜性不受其容易解決SP的事實的限制。