关于时间复杂度
先記住一下概念：
如果在多項式時間內能解決一個問題，這個問題就屬于 P 類問題。
如果在多項式時間內能驗證/猜出一個問題的一個解，這個問題就屬于 NP 類問題。
NP 問題與非 P 類問題是兩個概念。
簡單地說，如果可以用問題 B 的解法解決問題 A，問題 A 便可以約化為問題 B。
如果所有 NP 問題都可以在多項式時間內約化到某個 NP 問題，那么這個問題就屬于 NPC 問題。
(P=NP)問題：是否所有的 NP 問題都是 P 類問題。
是否所有問題都能在多項式時間內被解決呢？很遺憾，答案是否定的。比如，輸出從(n) 個互不相同的整數的全排列。不管你用什么方法，打印結果總得用階乘級的時間。不可解問題 (Undecidable Decision Problem) 甚至根本不可能找到一個正確的算法，如停機問題 (The Halting Problem)。
有人非說這種問題不是“正規”的問題，“正規”的問題是讓程序對一個問題回答 Yes 或 No（即判定性問題），或者求一個什么的最優值（即最優化問題）。那么，根據這個定義，求一個圖的哈密頓回路到現在還沒有找到多項式級的算法。事實上，這個問題就是我們后面要說的 NPC 問題，這里先按下不表。
接下來引入 NP 問題的概念。這個就有點難理解了，或者說容易理解錯誤。在這里強調，NP 問題不等于非 P 類問題。如果在多項式時間內能驗證/猜出一個問題的一個解，這個問題就屬于 NP 類問題。。
比方說某個求最短路徑的問題，問從起點到終點是否有一條小于 100 個單位長度的路線。你根據數據畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？我說，我 RP 很好，肯定能隨便給你指條很短的路出來。然后我就胡亂畫了幾條線，說就這條吧。你按我指的這條把權值加起來一看，嘿，神了，路徑長度 98，比 100 小。于是答案出來了，存在。別人會問他這題怎么做出來的，我就可以說，因為我找到了一個比 100 小的解。
在這個題中，找一個解很困難，但驗證一個解很容易（只需要 (O(n)) 的時間復雜度）。那么，只要我 RP 好，猜到的方案總是最優的，我一定能在多項式的時間里找到一個解，解決這個問題。這就是 NP 問題。
有沒有不是 NP 問題的問題，即不能在多項式時間里去驗證一個解？例如，我們知道哈密頓回路是 NP 問題，因為驗證一條路是否恰好經過了每一個頂點非常容易；但我要把問題換成這樣：試問一個圖中是否不存在哈密頓回路？這樣問題就沒法在多項式的時間里進行驗證了，因為除非你試過所有的路，否則你不敢斷定它“沒有哈密頓回路”。
之所以要定義 NP 問題，是因為通常只有 NP 問題才可能找到多項式的算法。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的算法。相信讀者很快可以明白，信息學中的號稱最困難的問題——
(P=NP) 問題實際上是在探討 NP 問題與 P 類問題的關系。
很顯然，所有的 P 類問題都是 NP 問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。關鍵是，人們想知道，是否所有的 NP 問題都是 P 類問題。我們可以再通過集合的角度來說明。如果把所有 P 類問題歸為一個集合 (P) 中，把所有 NP 問題劃進另一個集合 (NP) 中，那么，顯然有 (P ∈ NP)。現在，所有對 NP 問題的研究都集中在“(P=NP)問題”上，其實就一句話：證明或推翻 (P=NP)。
NP問題一直都是信息學的巔峰。很引人注目但難以解決。在信息學研究中，這是一個耗費了無數科學家大量時間和精力也沒有解決的終極問題，好比物理學中的大統一和數學中的歌德巴赫猜想。
目前為止大家還“啃不動”這個問題，但人們普遍認為 (P=NP) 不成立，也就是說，多數人相信，存在至少一個不可能有多項式級復雜度的算法的 (NP) 問題。人們如此堅信 (P≠NP)，是因為在研究 NP 問題的過程中找出了一類非常特殊的 NP 問題叫做 NP-完全 (NP-Complete) 問題，也即所謂的 NPC 問題。正是 NPC 問題的存在，使人們相信 (P≠NP)。下文將花大量篇幅介紹 NPC 問題，你從中可以體會到 NPC 問題使 (P≠NP) 很有可能成立。
為了說明 NPC 問題，我們先引入一個概念——約化 (Reducibility，又譯“歸約”)。簡單地說，一個問題 A 可以約化為問題 B 的含義即是，可以用問題 B 的解法解決問題 A，或者說，問題 A 可以“變成”問題 B。
《算法導論》上舉了這么一個例子。比如說，現在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應兩個問題，那么我們能找到一個“規則”，按照這個規則把解一元一次方程程序的輸入數據變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結果。這個規則即是：兩個方程的對應項系數不變，一元二次方程的二次項系數為0。按照這個規則把前一個問題轉換成后一個問題，兩個問題就等價了。
同樣地，我們可以說，哈密頓回路可以約化為 TSP(Travelling Salesman Problem，旅行商問題)：在哈密頓回路問題中，兩點相連即這兩點距離為 0，兩點不直接相連則令其距離為 1，于是問題轉化為在 TSP 中，是否存在一條長為 0 的路徑。哈密頓回路存在當且僅當 TSP 中存在長為 0 的回路。
“問題 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)，即變換輸入的方法是能在多項式的時間里完成的。約化的過程只有用多項式的時間完成才有意義。
從約化的定義中我們看到，一個問題約化為另一個問題，時間復雜度增加了，問題的應用范圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找復雜度更高，但應用范圍更廣的算法，來代替復雜度雖然低，但只能用于很小的一類問題的算法。再回想前面講的 P 和 NP 問題，聯想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若干小 NP 問題的一個稍復雜的大 NP 問題，那么最后
是否有可能找到一個時間復雜度最高，并且能“通吃”所有的 NP 問題的一個超級 NP 問題？
答案居然是肯定的。也就是說，存在這樣一個 NP 問題，所有的 NP 問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的 NP 問題都解決了。這種問題的存在難以置信，并且更加不可思議的是，這種問題不只一個，它有很多個，它是一類問題。這一類問題就是傳說中的 NPC 問題，也就是 NP-完全問題。NPC 問題的出現使整個 NP 問題的研究得到了飛躍式的發展。再次回到全文開頭，我們可以看到，人們想表達一個問題不存在能多項式時間內解決的高效算法時，應該說它“屬于 NPC 問題”。
NPC 問題的定義非常簡單。同時滿足下面兩個條件的問題就是 NPC 問題。
首先，它得是一個 NP 問題；
然后，所有的 NP 問題都可以約化到它。
證明一個問題是 NPC 問題也很簡單。先證明它至少是一個 NP 問題，再證明其中一個已知的 NPC 問題能約化到它（由約化的傳遞性，則 NPC 問題定義的第二條也得以滿足；至于第一個 NPC 問題是怎么來的，下文將介紹），這樣就可以說它是 NPC 問題了。
既然所有的 NP 問題都能約化成 NPC 問題，那么只要任意一個 NPC 問題找到了一個多項式的算法，那么所有的 NP 問題都能用這個算法解決了， P 也就等于 NP 了。因此，給 NPC 找一個多項式算法不大可能。因此前文才說，“正是 NPC 問題的存在，使人們更加相信 (P≠NP)”。我們可以就此直觀地理解，NPC 問題目前沒有多項式的有效算法，只能用指數級甚至階乘級復雜度的搜索。
順便講一下 NP-Hard 問題。NP-Hard 問題是這樣一種問題，它滿足 NPC 問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比 NPC 問題的范圍廣）。NP-Hard 問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發現了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復雜度更高從而更難以解決。
不要以為 NPC 問題是一紙空談，NPC 問題是存在的，確實有這么一個非常具體的問題屬于 NPC 問題。它就是邏輯電路問題。這是第一個 NPC 問題，其它的 NPC 問題都是由這個問題約化而來的。因此，邏輯電路問題是 NPC 類問題的“鼻祖”。
邏輯電路問題是指的這樣一個問題：給定一個邏輯電路，問是否存在一種輸入使輸出為True。
什么叫做邏輯電路呢？一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和密密麻麻的線組成。看下面一例，不需要解釋你馬上就明白了。
┌────┐
│輸入1├─→┐ ┌──┐
└────┘ └─→┤ │
│ or ├→─┐
┌────┐ ┌─→┤ │ │ ┌──┐
│輸入2├─→┤ └──┘ └─→┤ │
└────┘ │ ┌─→┤AND ├──→輸出
└────────┘┌→┤ │
┌────┐ ┌───┐ │ └──┘
│輸入3├─→┤NOT├─→────┘
└────┘ └───┘
這是個較簡單的邏輯電路，當輸入1、輸入2、輸入3分別為True、True、False或False、True、False時，輸出為True。
有輸出無論如何都不可能為True的邏輯電路嗎？有。下面就是一個簡單的例子。
┌───┐
│輸入1├→─┐ ┌──┐
└───┘ └─→┤ │
│AND ├─→┐
┌─→┤ │ │
│ └──┘ │ ┌──┐
│ └→┤ │
┌───┐ │ │AND ├─→輸出
│輸入2├→─┤ ┌──┐ ┌→┤ │
└───┘ └→┤NOT ├→──┘ └──┘
└──┘
上面這個邏輯電路中，無論輸入是什么，輸出都是False。我們就說，這個邏輯電路不存在使輸出為True的一組輸入。
回到上文，給定一個邏輯電路，問是否存在一種輸入使輸出為True，這即邏輯電路問題。
邏輯電路問題屬于NPC問題。這是有嚴格證明的。它顯然屬于NP問題，并且可以直接證明所有的NP問題都可以約化到它（不要以為NP問題有無窮多個將給證明造成不可逾越的困難）。證明過程相當復雜，其大概意思是說任意一個NP問題的輸入和輸出都可以轉換成邏輯電路的輸入和輸出（想想計算機內部也不過是一些 0和1的運算），因此對于一個NP問題來說，問題轉化為了求出滿足結果為True的一個輸入（即一個可行解）。
有了第一個NPC問題后，一大堆NPC問題就出現了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它就行了。后來，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題。現在被證明是NPC問題的有很多，任何一個找到了多項式算法的話所有的NP問題都可以完美解決了。因此說，正是因為NPC問題的存在，P=NP變得難以置信。P=NP問題還有許多有趣的東西，有待大家自己進一步的挖掘。攀登這個信息學的巔峰是我們這一代的終極目標。現在我們需要做的，至少是不要把概念弄混淆了。
總結
- 上一篇： 天眼查怎么查成绩
- 下一篇： /boot 目录介绍