時間復(fù)雜度
??此處我們分為兩類，多項式級的復(fù)雜度和非多項式級的復(fù)雜度。如O(1), O(log(n)), O(n^a) 等，我們把它叫做多項式級的復(fù)雜度，因為它的規(guī)模n出現(xiàn)在底數(shù)的位置；O(n!) 和 O(a^n) 型復(fù)雜度，它是非多項式級的，其復(fù)雜度計算機往往不能承受。當我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復(fù)雜度，非多項式級的復(fù)雜度需要的時間太多，往往會超時，除非是數(shù)據(jù)規(guī)模非常小。
約化(Reducibility，有的資料上叫“歸約”)
??簡單地說，一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。《算法導(dǎo)論》上舉了這么一個例子。比如說，現(xiàn)在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應(yīng)兩個問題，那么我們能找到一個“規(guī)則”，按照這個規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結(jié)果。這個規(guī)則即是：兩個方程的對應(yīng)項系數(shù)不變，一元二次方程的二次項系數(shù)為0。按照這個規(guī)則把前一個問題轉(zhuǎn)換成后一個問題，兩個問題就等價了。
?? “問題A可約化為問題B”有一個重要的直觀意義：B的時間復(fù)雜度高于或者等于A的時間復(fù)雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時間復(fù)雜度比A的時間復(fù)雜度還低了，那A的算法就可以改進為B的算法，兩者的時間復(fù)雜度還是相同。正如解一元二次方程比解一元一次方程難，因為解決前者的方法可以用來解決后者。
??很顯然，約化具有一項重要的性質(zhì)：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。
P問題
??如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。
NP問題
??NP問題不是非P類問題。NP問題是指可以在多項式的時間里驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。很顯然，所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解。
??人們想知道，是否所有的NP問題都是P類問題。即 P=NP（這個有待驗證，不過人們普遍認為，P=NP不成立，也就是說，多數(shù)人相信，存在至少一個不可能有多項式級復(fù)雜度的算法的NP問題。）
NPC問題
??同時滿足下面兩個條件的問題就是NPC問題。首先，它得是一個NP問題；然后，所有的NP問題都可以約化到它。證明一個問題是 NPC問題也很簡單。先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足。
??既然所有的NP問題都能約化成NPC問題，那么只要任意一個NPC問題找到了一個多項式的算法，那么所有的NP問題都能用這個算法解決了，NP也就等于P 了。因此，給NPC找一個多項式算法太不可思議了。因此，前文才說，“正是NPC問題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效算法，只能用指數(shù)級甚至階乘級復(fù)雜度的搜索。
NP-Hard問題
??NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比 NPC問題的范圍廣）。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發(fā)現(xiàn)了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復(fù)雜度更高從而更難以解決。
第一個NPC問題：
??一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和密密麻麻的線組成。給定一個邏輯電路，問是否存在一種輸入使輸出為True，這即邏輯電路問題。邏輯電路問題是第一個NPC問題。其它的NPC問題都是由這個問題約化而來的。因此，邏輯電路問題是NPC類問題的“鼻祖”。
??有了第一個NPC問題后，一大堆NPC問題就出現(xiàn)了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它就行了。后來，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題?，F(xiàn)在被證明是NPC問題的有很多，任何一個找到了多項式算法的話所有的NP問題都可以完美解決了。因此說，正是因為NPC問題的存在，P=NP變得難以置信。P=NP問題還有許多有趣的東西，有待大家自己進一步的挖掘。
