什麼是P，NP和NPC問題？

• 2020 年 8 月 14 日
• 筆記

P問題，NP問題，NPC問題？這些都是電腦科學領域，關於演算法方面的術語。在認識這些術語之前，建議同學們先認真學習一下演算法的時間複雜度，因為演算法的時間複雜度與P，NP和NPC問題高度相關。

什麼是P問題？

P是英文單詞Polynomial的首字母，多項式的意思。

如果問題可以通過一個多項式複雜度的演算法解決，這個問題就可以稱為P問題。多項式複雜度意味著，演算法的計算量在一個可以接受的範圍內，我們很容易就能得到計算結果。如果是指數級複雜度的演算法，有可能在問題規模達到一定級別的時候，就更本算不出來。

什麼是NP問題？

NP的全稱為 Non-deterministic Polynomial，而不是Non-Polynomial。所以，NP問題並不是非P問題。

NP問題是指可以在多項式的時間裡驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間裡猜出一個解的問題。Non-deterministic Polynomail直譯的意思是，不是確定的多項式，即不確實是否是P問題。如果能夠找到一個多項式複雜度級別的演算法，那麼這個問題就是P問題，如果找不到，但是可以在多項式複雜度級別的情況下驗證，就是NP問題。

網上看到一個牛人寫的例子，用來理解NP問題：

比方說，我RP很好，在程式中需要枚舉時，我可以一猜一個準。現在某人拿到了一個求最短路徑的問題，問從起點到終點是否有一條小於100個單位長度的路線。它根據數據畫好了圖，但怎麼也算不出來，於是來問我：你看怎麼選條路走得最少？我說，我RP很好，肯定能隨便給你指條很短的路出來。然後我就胡亂畫了幾條線，說就這條吧。那人按我指的這條把權值加起來一看，嘿，神了，路徑長度98，比100小。於是答案出來了，存在比100小的路徑。別人會問他這題怎麼做出來的，他就可以說，因為我找到了一個比100 小的解。在這個題中，找一個解很困難，但驗證一個解很容易。驗證一個解只需要O(n)的時間複雜度，也就是說我可以花O(n)的時間把我猜的路徑的長度加出來。那麼，只要我RP好，猜得准，我一定能在多項式的時間裡解決這個問題。我猜到的方案總是最優的，不滿足題意的方案也不會來騙我去選它。這就是NP問題。

P問題肯定是NP問題，因為P問題有多項式複雜度級別的演算法來解，就一定能在多項式複雜度級別的情況下驗證。

再來一個理解NP問題的例子：

給出 n 個城市和兩兩之間的距離，求找到一個行走方案，使得到達每個城市一次的總路程最短。我們可以這樣來「猜測」它的解：先求一個總路程不超過 100 的方案，假設我們可以依靠極好的運氣「猜出」一個行走路線，使得總長度確實不超過 100，那麼我們只需要每次猜一條路一共猜 n 次。接下來我們再找總長度不超過 50 的方案，找不到就將閾值提高到75…… 假設最後找到了總長度為 90 的方案，而找不到總長度小於 90 的方案。我們最終便在多項式時間內「猜」到了這個旅行商問題的解是一個長度為 90 的路線。它是一個 NP 類的問題。

也就是說，NP 問題能在多項式時間內「解決」，只不過需要好運氣。顯然，P 類問題肯定屬於 NP 類問題。

當然，也存在不是NP問題的問題，即你猜到了解，但是沒用，因為你不能在多項式的時間裡去驗證它。

之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的演算法。我們不會指望一個連在多項式複雜度情況下驗證一個解都不行的問題，存在一個解決它的多項式複雜度級的演算法。資訊學中的號稱最困難的問題——「NP問題」，實際上是在探討NP問題與P類問題的關係，即 \(P=NP\) ，還是 \(P≠NP\) 。

什麼是NPC問題？

NPC就是NP完全問題，C是Complete的首字母。

為了說明NPC問題，我們先引入一個概念：約化（Reducibility，化簡的能力，有的資料上叫「歸約」）。

簡單地說，一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以「變成」問題B。

《演算法導論》上舉了這麼一個例子。比如說，現在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那麼我們說，前者可以約化為後者，意即知道如何解一個一元二次方程那麼一定能解出一元一次方程。我們可以寫出兩個程式分別對應兩個問題，那麼我們能找到一個「規則」，按照這個規則把解一元一次方程程式的輸入數據變一下，用在解一元二次方程的程式上，兩個程式總能得到一樣的結果。這個規則即是：兩個方程的對應項係數不變，一元二次方程的二次項係數為0。按照這個規則把前一個問題轉換成後一個問題，兩個問題就等價了。

再來一個約化的例子：

在與數不盡的問題搏鬥的過程中，人們有時候會發現，解決問題 A 的演算法可以同時用來解決問題 B。例如問題 A 是對學生的姓名與所屬班級同時排序，問題 B 是對人們按照姓名做排序。這時候，我們只需要讓班級全都相同，便能照搬問題 A 的演算法來解決問題 B。這種情況下，數學家就說，問題 B 能歸約為問題 A。

「問題A可約化為問題B」有一個重要的直觀意義：B的時間複雜度高於或者等於A的時間複雜度。也就是說，問題A不比問題B難。

這很容易理解。既然問題A能用問題B來解決，倘若B的時間複雜度比A的時間複雜度還低了，那A的演算法就可以改進為B的演算法，兩者的時間複雜度還是相同。正如解一元二次方程比解一元一次方程難，因為解決前者的方法可以用來解決後者。

很顯然，約化具有一項重要的性質：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。

約化的標準概念：如果能找到這樣一個變化法則，對任意一個程式A的輸入，都能按這個法則變換成程式B的輸入，使兩程式的輸出相同，那麼我們說，問題A可約化為問題B。

當然，我們所說的「可約化」是指的可「多項式地」約化（Polynomial-time Reducible），即變換輸入的方法是能在多項式的時間裡完成的。約化的過程只有用多項式的時間完成才有意義。

從約化的定義中我們看到，一個問題約化為另一個問題，時間複雜度增加了，問題的應用範圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找複雜度更高，但應用範圍更廣的演算法來代替複雜度雖然低，但只能用於很小的一類問題的演算法。聯想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能「通吃」若干小NP問題的一個稍複雜的大NP問題，那麼最後是否有可能找到一個時間複雜度最高，並且能「通吃」所有的 NP問題的這樣一個超級NP問題？

答案居然是肯定的。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那麼所有的NP問題都解決了。這種問題的存在難以置信，並且更加不可思議的是，這種問題不只一個，它有很多個，它是一類問題。這一類問題就是傳說中的NPC問題，也就是NP完全問題。如果我們給其中任何一個NPC問題找到了多項式級別的演算法，就相當於證明了 \(P=NP\)。但是人們至今沒有成功找到。

NPC問題的出現使整個NP問題的研究得到了飛躍式的發展。我們有理由相信，NPC問題是最複雜的問題。人們想表達一個問題不存在多項式級別的高效演算法時，應該說它「屬於NPC問題」。

既然所有的NP問題都能約化成NPC問題，那麼只要任意一個NPC問題找到了一個多項式的演算法，那麼所有的NP問題都能用這個演算法解決了，\(NP=P\) 。因此，給NPC找一個多項式演算法太不可思議了。因此，正是NPC問題的存在，使人們傾向於相信 $P≠NP $。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效演算法，只能用指數級甚至階乘級複雜度的搜索。

這部分最後，NPC問題的定義。同時滿足下面兩個條件的問題就是NPC問題。

首先，它得是一個NP問題；

然後，所有的NP問題都可以約化到它。

有了第一個NPC問題後，一大堆NPC問題就出現了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它就行了。

實在太抽象了。。。。

NP-Hard問題

NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定滿足第一條（就是說，NP-Hard問題要比NPC問題的範圍廣）。

NP-Hard問題同樣難以找到多項式的演算法，它不一定是NP問題。即使NPC問題發現了多項式級的演算法，NP-Hard問題有可能仍然無法得到多項式級的演算法。事實上，由於NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間複雜度更高從而更難以解決。

以上問題反覆閱讀幾次，相信足夠理解什麼是P問題，什麼是NP問題，什麼NPC問題。