本文來源:微信公眾號:算法與編程之美,作者:黃章魚
地址:https://mp.weixin.qq.com/s?__biz=MzI5MTQ5NDY1MA==&mid=2247492509&idx=1&sn=d5ad5d7ad663d60d5fe0ba823c8028ea
一概念引入
1.1時間複雜度
在計算機處理一個問題時，往往需要一定的時間，假設把這個問題複雜化（將這個問題進行擴展），那麼把計算機處理這類問題的時間變化速率，稱為解決這種問題所用算法的時間複雜度。例如，一個枚舉一定範圍內的數字的問題，計算機所用時間會隨著範圍的變化而線性變化，由於是簡單的枚舉，所以時間複雜度可以記為O(n)，n可以代表這個範圍大小。在計算機處理問題時，由於算法設計不同，對應的時間複雜度也不一定相同。
1.2多項式級時間和非多項式級時間
在眾多的時間複雜度中，根據其表達式的特點，可以大致將它們劃分為兩個範疇，一個是多項式級一個是非多項式級。它們各自表示什麼意思呢？還記得高中數學中學習的函數嗎，在學習不同函數時，最常做的一件事是觀察它們的圖像變化，可以發現，x作為底數的圖像和x作為指數的圖像在後期的變化簡直有天壤之別。這也正是需要將時間複雜度劃分的原因（多項式級的時間複雜度在後期變化遠小於非多項式級），將n作為底數的時間複雜度歸為多項式級，n作為指數的歸為非多項式級。例如O(n)、O(log(n))、O(n^a)等就是多項式級的時間複雜度，像O(n!)和O(a^n)就是非多項式級的複雜度。對於計算機來說需要處理的問題往往是很龐大的，如果採用非多項式級複雜度的算法，那麼將浪費很大的資源。
1.3 P問題
在解釋了多項式級和非多項式級時間複雜度之後，P問題的概念就簡單了。對於眾多的問題，通常把能夠使用多項式級時間複雜度算法解決的問題稱為P問題。
二什麼叫NP問題
2.1 約化
一般，問題A可以約化為問題的B的解釋是可以用解決問題B的方法解決問題A。簡單的說，也就是問題A是問題B的另一種形式，且問題A的複雜程度要小於等於問題B。就像解方程組的問題，假如你會解二元一次方程組，那麼你一定會解一元一次方程，在這個例子中，一元一次方程就是問題A，二元一次方程組就是問題B，問題A可以看作是問題B中另一個自變量係數為零的特殊“二元一次方程組”。那麼解二元一次方程組的問題是否可以約化成解三元一次方程組問題呢？答案很明顯是可以，同理的，解一元一次方程也可以約化成解三元一次方程組問題。可以看出，約化是具有傳遞性的，且如果問題A可以約化成問題B，則問題B的時間複雜度一定大於等於問題A的時間複雜度。
2.2 P=NP？
有了約化這個概念之後，可以發現所有的P問題都可以約化成NP問題。因為一個問題既然可以在多項式級時間內解決，那麼對於驗證一個解的正確性是肯定可以做到的，因此，如果把P問題看作一個集合P，NP問題看作另一個集合NP，則P包含於NP。那麼P=NP嗎？答案尚未確定，這也是現在所常研究的“NP問題”的實質，這是一道世界難題，一旦解決這個問題，那麼就意味著可以找出具有多項式級時間複雜度的算法來解決NP問題。
三新的問題
3.1 NP與NPC問題
前文提到確定P=NP的問題是一道世界難題，這是因為已知的NP問題遠遠多於P問題，且運用約化的概念，是否所有的NP問題也可以約化成同一個問題呢？這個問題的答案早已被證實是可行的，而且這種問題還不止一個，它們被稱為NPC問題。很明顯，NPC問題具有兩個特點：它滿足NP問題的條件，且所有的NP問題都可以約化成它。既然所有的NP問題都可以約化成NPC問題，那麼只要能夠在多項式級的時間複雜度下解決一個NPC問題，所有的NP問題也都能用同樣的方法解決了，那麼NP問題也就成了P問題。但是給一個NPC問題找出一個多項式級時間複雜度的算法的工作至今仍在進行中，因此，還是很難證明P=NP。
3.2 NPC案例
邏輯電路是一個典型的NPC問題，什麼叫做邏輯電路呢？一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和密密麻麻的線組成。在邏輯電路問題中，需要找到不同輸入的組合，使得輸出的結果滿足要求。
圖3.1.1 邏輯電路示意圖
邏輯電路之所以是一個NPC問題，是因為你無法在多項式級的時間複雜度內解決它，但是要想驗證一個解的正確性是很簡單的，無論這個邏輯電路多麼複雜，仍然只需要將每個點的狀態帶入進去就可以驗證，屬於O(n)的時間複雜度。
3.3 NPC與NP-Hard問題
NP-Hard問題和NPC問題的不同在於NP-Hard問題不一定是NP問題，因此，NP-hard問題的範圍要大於NPC問題，同時，要為NP-Hard問題找到一個多項式級時間複雜度的算法也更加困難，這也是“Hard”的含義，可能NPC問題能夠找到多項式級時間複雜度算法的時候NP-Hard問題仍然還無法完成這項工作。
四 P、NP、NPC、NP-Hard問題的關係
在上述介紹中，可以知道，P問題包含於NP問題中，NPC問題同時包含於NP問題和NP-Hard問題，也就是它們的交集，則它們的關係可以如下表示。
圖4.1 P、NP、NPC、NP-hard問題關係圖
本文來源:微信公眾號:算法與編程之美,作者:黃章魚
地址:https://mp.weixin.qq.com/s?__biz=MzI5MTQ5NDY1MA==&mid=2247492509&idx=1&sn=d5ad5d7ad663d60d5fe0ba823c8028ea
