吳邦一, 2006/8
目錄
計算機科學家努力尋找解決問題的計算方法，經由不斷的發明改進，有一些問題找到了有效率的方法，同時也證明了方法的最佳性，也就是證明了不可能存在更好的方法，例如排序問題。所謂排序問題是這樣定義的：輸入一群n個整數，請將此n個整數由大而小排列。排序問題是一個應用很廣，因此很重要的問題，對於此問題，我們已經找到了時間複雜度為O(nlogn)的算法，同時也證明在目前的計算模式下不可能有更佳的方法。
Remark: 計算機科學中評估複雜度以Big-O的方式來表示，簡單的說複雜度為O(f(n))表示當資料量n很大時，計算時間為f(n)的一個常數倍。例如快速排序法的時間複雜度為O(nlogn)，代表當資料量超過某個界限值之後，他的計算時間約與nlogn成正比增加。
再舉一個稱為Selection problem的例子：輸入一群n個整數以及任意一個介於1~n的整數，請找出此n個數中第k大的數字。像這樣一個"簡單"問題，很多人一看之下就可以提出一個算法：先將此n個數字由小到大依序排好，再挑出第k大的數字。不錯，這是個正確的算法，但卻不是最有效率的算法，我們來看看這樣的一個方法所需要的時間為何。我們先做排序所以花掉O(nlogn)的時間，然後挑出第k大的數，這個步驟花的時間相對少而可以不計，因此整個計算方法的時間複雜度為O(nlogn)。這是個有效率的方法了（複雜度為多項式函數），我們之所以說他不是最好，是因為有人找出時間複雜度為O(n)的方法。我們這裡並不打算介紹這個方法，但是有一點可以說明，通常我們在考慮一個算法是否可以改善時，會先去思考他是否「殺雞用了牛刀」。也就是說，做了不必要的計算。以這個selection問題來說，直覺上，挑選第k大的數字只關係到某個數字前後有幾個，而無關乎那兩群數字內部的關係，因此應該可以不需要將所有的數字排序。
另一個這裡主要要說明的事情是，如果一個人發明了一個O(n)的算法，我們如何可以稱他是最佳的方法呢？我們必須證明：「不管任何人來做都不會更好」，也就是此問題的複雜度就剛好是這個演算法的複雜度。這可不是件簡單的事情，科學或是說數學上要證明一個性質有幾種常用的方法。
如果對於有限的成員，我們可以列舉。例如說，你要證明這個班級上的學生沒有人超過200公分，我們可以把全部的學生一一量身高。如果要證明的對象太多，也可以先把對象劃分為一群一群，再來列舉證明，以簡化證明的過程。但是對於無限的成員，這招可行不通了。常用的方式有歸納法以及矛盾證明法。
在證明selection問題的複雜度時，我們可以用矛盾證明法，在這裡也稱為「敵對論證」。假設有一個方法A可以不需要O(n)（我們稱為線性時間）的時間就可以找出答案（第k大的數），他意味著不需要將全部的輸入資料看完就可以得到答案，因為如果將全部的輸入資料看一遍就需要線性時間了，那麼我們站在一個敵對的立場，一定可以建造出一群資料使得A方法找出的答案是錯的，如此來得到一個矛盾，也就證明了存在這樣一個演算法的假設是錯的。
有很多的問題的複雜度至少是線性時間，都可以利用類似的方法來證明。當然也有些問題他的複雜度比線性時間還要小，這些問題通常是對輸入資料有所假設。例如，在一群排好序的數字中尋找是否存在某個數字。我們可以利用二分搜尋法：每次比較中間數至少可去除一半的數字，而在logn的時間內確定所要搜尋的數字是否在其中。對於像排序那樣問題的複雜度並不是利用簡單的矛盾法就可以證明，而需要一些離散數學的知識與技巧，我們這裡不打算說明。
上面提到的些問題，我們皆已經得到一個有效率的算法，也證明他的最佳性。事實上，有更多的問題他的複雜度還是未知的。
如果是一個已經找出有效率解法的問題，不知其複雜度只是美中不足而已，就好比如果你已經有個很不錯的女（男）朋友，你並不一定需要知道他會不會是你這輩子能碰到的最好的。但是有些問題一直找不到有效率的解法，那麼去了解有效率的解法是否存在，就變得格外的重要。舉幾個這樣的例子。
Partition Problem：輸入一群整數，請問是否可以將這一群整數分成兩堆，使得兩邊的總合是相等的？
這個問題聽起來很簡單，但是截至目前為止，並無人能夠找到一個有效率的解法。再看一個例子：
Hamiltonian Problem：假設有若干城市，某些之間有道路相連，請問是否存在一條路徑走過每個城市恰好一次。
同樣的，這個問題的複雜度至今無人知道，也還沒有快速的解法。我們再舉一個很重要的問題，稱為滿足性問題（Satisfiability）。
假設你開了一家餐廳，有一天，來了一群客人，每個人都開出一些條件，身為老闆的你需要找出：「是否能夠開出一桌菜色滿足所有的人？」客人也不是太難伺候，每個人所開的若干條件，只需要有一項滿足就可以，但是必須滿足每個人至少一個願望，不可以有人一項要求都達不到。舉例來說：
A客人：有魚 或
有蝦 或 沒有香蕉
B客人：有青菜 或 沒有魚
C客人：沒有青菜
為了簡化起見，我們假設每一個條件都是「有…」或「沒有…」。以這個例子來說，我們只要「沒有青菜且沒有魚且有蝦」，就可以滿足所有的人，當然，「沒有青菜且沒有魚且沒有香蕉」也可以滿足所有的人，我們只想問可不可能滿足所有人就好了。我們可以很容易想像有些狀況答案是不能的，例如：
A客人：有魚 或
有青菜
B客人：有青菜 或 沒有魚
C客人：沒有青菜
在這個例子中，身為老闆的你就需要判斷出不存在「滿足所有人至少一個條件」的方式。這個問題是一個邏輯的問題，他的抽象描述是這樣的：
假設有n個布林變數X1,X2,...,Xn，所謂布林變數指的是他的值是True或False，我們有m個條件（clause），每一個條件都是由若干個變數或是他的否定以「或」的方式組合起來的，例如，
X1 or (-X2) or (X5)
其中的(-X2)表示X2的否定
Satisfiability問題（簡稱SAT）是問說：有沒有一種變數的指定方式（也就是給每個變數指定其為True或False），使得所有的clause都被滿足。
SAT問題是屬於NP族群的問題，在猜測了每個變數的真值之後，我們很容易在多項式時間內驗證猜測的解是否正確。Stephen A. Cook (1982 Turing Award)在他1971年的一篇論文中證明了一件事情：
所有屬於NP的問題都可以轉換為某一個SAT問題，而如果SAT問題是易解的（屬於P），那麼所有的NP問題都是易解的（屬於P），也就是說，如果SAT屬於P那麼NP=P。
這並不是一件容易的事，要將一個問題轉換為另一個問題或許還不算太難，但是Cook所做的是：「將所有的NP內的問題全部都可轉換為SAT問題」。他是怎麼做得到的呢？以事後諸葛的角度倒也不是那麼神奇。SAT問題是一個邏輯的問題，證明的內涵是：假設任何一個問題是在NP內，則會存在一個非確定性的杜林機可以計算它，然後Cook將此機器的運作過程轉化為SAT的邏輯問題。
此話說來簡單，證明的過程卻也不是那麼容易。在計算理論的角度上來看有三種問題可以說是等價的：
1. 計算一個是與否問題的答案
2. 辨識一個字串是否屬於某個字串集合（語言）
3. 搜尋問題，一個很容易計算的函數的反運算，例如兩數相乘是個容易計算的函數而其反運算數指找出個數的因數或者說將某數分解因數
Leonid Levin在1973年發表了一個以搜尋問題為基本而類似於Cook的結果，據Levin自己的陳述，他在1971年即已經得到此結果，目前有時我們稱該定理為Cook-Levin定理。
乍看之下Cook-Levin定理的用處似乎是讓我們更容易去證明NP=P，因為只要能證明一個問題在P，中就可以證明NP中那無限多個問題均在P中，如果沒有這個定理，我們似乎很難去證明那一堆子問題都屬於P這個類別。但是截至目前為止，他的發展卻是朝向另外一個方向。
其關鍵的一步在於Richard M. Karp (1985 Turing Award)在1972年證明了21個重要的問題都和SAT問題具有一樣的性質，也就是說其中任何一個問題如果屬於P，那麼就會得到NP=P的結果。
Karp的結果的重要性不只在於證明出那21個重要問題的難度，影響更大的是他證明的方法開啟了如何證明其他問題也是同樣的難的方法。在此之後，更多的問題也一一被證明是具有相同的難度，因此這些問題形成了一個類別，他們都具有相同的性質：「如果其中任何一個問題屬於P則NP=P」，而且，依據定義，這些問題彼此之間都可以相互轉換，雖然彼此之間看起來有時並非如此相似。初期這個類別有幾種稱呼方式（科學家很喜歡取名字），經過Donald Ervin Knuth（高德納）(1974 Turing Award) 的一番努力後，此類別定名為NP-Complete（以下簡稱NPC）。Michael R. Garey與David S. Johnson在1979年所著的Computers and Intractability: A Guide to the Theory of NP-Completeness一書中，對於NPC的理論、證明方法、延伸問題都做了很豐富而詳盡的整理與說明，是直到今日理論計算機研究者的寶典，書中尤其蒐列了數以百計的重要NPC問題，到今天，NPC的問題已經列不勝列了。
而這些問題一一出現，越來越讓我們相信NP其實是不等於P的，由此可見Cook、Levin與Karp三人所做的結果的影響力之大，雖然在Wikipedia（維基百科）中稱NPC定理為Cook's Theorem 或Cook-Levin
Theorem，但是Karp的貢獻可能更大。這就好像即使有Turing的杜林機器模型與von Neumann（馮紐曼）的儲存程式架構，如果沒有IC的發明，電腦的影響力不可能如今天這般。
簡單的說，NPC定理在指明有一群問題，他們是NP這個族群中最難的問題。大家說NPC定理很重要，我們要回頭問：「證明一些問題很難為什麼很重要？」科學的發展是要造福人類而不只是玩數學證明，計算機科學家是要找出以計算機解決問題的方法而不是只告訴我們這個問題很難。
有許多問題，不管他是否在NP中，我們一直找不出有效率的解法，但是問題還是要解決，因此我們會去找一些其他的解決方法，例如說，對於一些最佳化問題，我們不再要求所得到的解是最佳的，而可以是一個還可以的解；或者，如果在可允許的情況下，我們容許花多一點的時間來計算最佳解。但是這樣做難免會有疑慮：我花了很多的努力去設計一個並非求最佳解的計算方法，搞不好其實有一個很簡單的算法就可以求得最佳解，我找不出來不見得不存在啊，可能只是我不夠聰明。因此我們必須在乎此問題的難度，但是難的是，很多重要問題又證明不出來他不可能存在有效率的解。
NPC的重要性在於，一但證明了某個問題屬於NPC，我們就可以知道，這個問題的難度不是只有我不知道，而是一大堆的著名科學家都不知道。因此，在今天來說，對於一個NPC問題，科學家們可以同意不必去尋求計算最佳解的計算方法，而可以努力於其他的方法。