未來數學家的挑戰
計算量問題
楊照崑;楊重駿
一、前言 二、計算量 三、P 之外？ 四、古克定律與 NP-completeness 五、NP-complete 問題之近似解 六、NP-hardness 與圍棋 七、結論
一、前言
有數學家說過「一個好的問題勝過十個好解答」。因為解答一出，此問題已是到了終點，對不斷求創新的人們而言，已不構成挑戰。而新的問題是源頭活水，能開拓新的境界。多數人都不願沉醉在好的解答中不斷的玩味，而希望找到新的問題，不斷的思考，摸索。
大家在《數播》上已看見了不少好的問題，尤其最近康明昌教授談到的費馬定理，幾何三大難題，都是極有趣的問題。有的已有了解答，有的尚待解決。除了上面的題目外，像四色問題（即任何一個地圖只要用四種顏色就可以把國界分開），五次以上方程式的公式解，及數論上質數分佈問題，都曾在職業及業餘數學家的心目中佔有相當的地位。本文所要介紹的是一個最近（1970年代開始）一種許多數學家及電子計算機學家所關心的大問題──NP 問題。 NP 所代表的意思，你看完本文之後自然會明白，現在你不妨記住「NP-hard」這個偉大的字。將來如果你對某人說你的問題是「NP-hard」，他也許就要對你刮目相看了，NP-hard 不但代表 hard（難），而且是 NP 的難！
NP 問題的代表問題之一是售貨員旅行問題 (traveling salesman problem)。有一個售貨員要開汽車到 n 個指定的城市去推銷貨物，他必須經過全部的 n 個城。現在他有一個有此 n 城的地圖及各城之間的公路距離，試問他應如何取最短的行程從家中出發再到家中？
圖1 售貨員之地圖，A,B,C,… 表城名，數字表兩城之間之里數。
如圖1中，A,B,C,…,G 表示 7 個城市，而售貨員要從 A 城出發再回到 A 城並訪問 B,C,…,G，所有的城，一個可行的方法是
由於電子計算機的發展，有許多以前認為枉費時的計算，像行列式之值，反矩陣，高次方程式的解，都可以在極短的時間內解決。但也突然出現了一些新問題，連大型計算機也望之興嘆。像售貨員問題，因為找不到比硬排好得很多的做法，使得數學家們開始想要證明，根本找不到比硬排好得很多的做法。這個證明至今尚未找到。就像以前一角三等分問題一樣，既然找了幾千年找不到用圓規直尺三等分任一角的方法，也許我們可以證明絕對不可能用圓規直尺三等分一角。現在我們要證明絕不可能寫一個計算機程式大大的簡化售貨員旅行問題。與三等分一角問題不同的是，前者是一種數學上的好奇，而當今的問題與實際用途卻有密切的關連。
在此我們一直強調一個好得很多的方法。原因是對這類的問題，你若能計算快一倍或十倍、千倍，往往起不了什麼大作用，好像剛才的二十城旅行問題，即使快了千倍，仍需三年的計算時間，而再加三城立刻就把這個計算法的效果抵消了，因此我們所要的是計算量基本層次的減少，這就是我們在下一節所要討論的。
未來數學家的挑戰
計算量問題 （第 2 頁）
楊照崑;楊重駿
計算量，顧名思意，是指解決某問題所需要計算的時間，但因每個複雜問題的計算往往都要經過許多不同的運算，除加減乘除四則外，還要包含比較，取數據，存數據等等，若仔細計算起來，十分困難，一般都只繪出一兩個主要的量，加以統計，以上節中售貨員旅行問題為例，其主要的工作是對每一個排法加起總路徑之長，因對 n 城而言，有 (n-1)! 的排法，我們就定其計算量為 O(n!)，即在 n! 之層次（order 即 O 縮寫之來源）之內。
舉二個例子，我們若要求 n 個數的和或平均值，則其計算量為 O(n)。但若我們要把 n 個數字依次排列，則其計算量會因做法的不同而有相當的差別，一個直接了當的方法是，先求出最大的（比 (n-1) 次），再從不是最大的中間求次大的（比 (n-2) 次），再求第三大的（比 (n-3) 次），……如此一共比了
一般計算量的層次多以下表來區分，
本節之題目有點不平常，我們的目的是提醒讀者本文中常用之英文大寫的 P 是一個凡能用 O(nk) 計算量解決之問題之集合。而 P 之外加一個問號係指到目前為止，我們尚不知道 P 之外是否是一個空集合。
到目前為止，除了售貨員旅行問題之外，已經有上百有趣或有用的問題，無法用 O(nk) 的計算量來解決，我們在此列舉幾個例子。
問題1：售貨員旅行問題（甲） 即第一節所述之問題，不再重複，不過假定所有距離均為正整數 3 。
問題2：售貨員旅行問題（乙） 與第一題之條件相同，但現在有一個給定之正整數 B，問題是是否存在一條路徑其總距離不大於 B。（問題1與問題2在表面上相似，但在以後的理論上有很大的不同） 問題3：背袋問題（甲） 有物體 n 個，各重 w1,w2,…,wn，今欲將它們分為二袋，試問如何分法可使兩袋之重量最為接近。（不妨假定 wi 皆為正整數，這並未失去一般性。) 問題4：背袋問題（乙） 如上題，並給定一正整數 B，試問可否選出若干 wi，使其和現在可以看出這類問題的一般結構了。很顯然的，有些是極有用的問題，而有些可以轉換成有用的問題。例如舞伴問題，若把男孩與女孩換成工人與工頭，或醫生與病人就有大用了。這些問題到目前沒有一個可以證明是屬於 P 的，大家都猜測它們可能在 P 之外，即其計算量是呈指數增加的。
在60年代，已有些人把某些問題歸於一類了，即是幾個問題是互依的，若其中之一若屬於 P，則其他幾個也屬於 P，其證明方法大都是證明兩個互依問題中間有一個只需要用 O(nk) 時間來完成的橋樑。直到1971年古克 (Stephen A. Cook) 發表了〈The Complexity of Theorem Proving Procedures〉才把 P 之外約問題歸成了三大類，即 NP, NP-complete 及 NP-hard 4 ，現在談古克定律。
未來數學家的挑戰
計算量問題 （第 4 頁）
楊照崑;楊重駿
古克定律的證明很難，就是瞭解它也不容易，我們將從幾個角度來看這個問題，試著去暸解它。它的主要結果是把前節那類問題大部歸於一個較易證明的集合，稱之為 NP，而在 NP 中找到一批互依的問題稱之為 NP-complete 類並得到下面的結果。
1. 若有一個 NP-complete 問題可以用 O(nk) 計算量來解決，則全體的 NP 問題都可以用 O(nk) 之計算量來解決，即 1' 若有一個 NP-complete且 ，則 P=NP。
又換句話說，NP-complete 是 NP 中的難題，NP-complete 解決了 5 ， NP 就解決了。但若有一個屬於 NP 而不屬於 NP-complete 的問題解決了，則其他的 NP 問題不一定可以解決。
什麼叫做 NP？NP 是英文 nondeterministic polynomial 的縮寫，意思就是非確定性的多項式時間。要暸解這個字。我們先看一看普通計算機的作用。
現在已知用一個計算機，要解決售貨員旅行問題非常困難，但若我們有許多計算機同時用，是否可以快到把原問題在 O(nk) 時間內解決？「許多」，不是一、二，多一二個是於事無補的，多百個千個仍是杯水車薪，不能有很大的作用，因為就是一千個機子可以分開做，也最多只能快一千倍，在第一節內已說過，幫助不大。因此計算機學家先放眼望去，乾脆允許你可以無限的增加機器。現在我們要注意的是並不是有了無限多的機器所有的問題就可以立刻解決了，因有的問題有先後次序，例如在算下式的時候
現在要記住的是由於無橫向連絡，在所有路徑的距離都有了之後，並沒有解決售貨員問題（甲），因為不知誰是最短（若加以比較以求最短距離，則要 O(n!) 個比較），因此我們不能說售貨員旅行問題（甲）是一個 NP 問題。但上節問題2，售貨員旅行問題乙，任何一個單線都可以知道它的總距離是否不大於 B，因此每單線都有一個「Yes」或「No」的答案。只要有一個「Yes」的答案，我們即知道本問題已解決，故問題二是一個 NP 問題。在單線作業中，每個機子可以作三件事。
目前答案不明確，大家各自作業。
某線已找到答案，立刻叫停，大家停止作業，解題完畢。 此路不通，本線不再作業，但不叫停，別線仍然作業。從上項作用，很容易看出找出答案的計算時間即某線叫停的時間，亦即任何一個有「Yes」答案線中計算量之總和，也就是說找到答案「捷徑」上所需的時間。易言之，在一非確定性計算機系統下，其子機像有「猜測」到捷徑的功能。若在任何計算步驟中，某人猜了一個答案，而計算機可以在 O(nk) 時間內回答「Yes」或「No」，這個問題即是一個 NP 問題。再以售貨員旅行（甲）及圖1為例，若你猜一個路徑
由這兩個定義，讀者不難看出問題2,4,6,7,8,9（乙）與10皆為 NP 問題，特別是問題9之（甲），（乙），其實是一樣的問題，但如果你猜二個 m,n，立刻就可知道 a 是否是 mn。
古克定理的關鍵在證明若一種叫滿足問題 (Satisfactability Problem) 的例子屬於 P，則所有 NP 問題均屬於 P（即此問題屬於 NP-complete），令 ,+,-（且，或，反）表三個基本的邏輯運算（即對0與1邏輯符號而言，,,除了1+1=1之外，+， 與一般代數之加乘相同）。令 f 為一個含有 n 個邏輯變數 (u1,u2,…,un) 的函數。假如我們可以找到一組 u1,u2,…,un，使得 f(u1,u2,…,un) = 1，則 f(u1,u2,…,un) 稱為可滿足。例如
直覺上，這類問題除了將 u1, u2,…,un 一個一個以 0,1 代入檢查 2n 次之外，顯無捷徑可循，古克1971年之論文即證明這是一切 NP 問題之母。
古克定理： 滿足問題為 NP-complete。
現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。
未來數學家的挑戰
計算量問題 （第 5 頁）
楊照崑;楊重駿
NP-complete 問題既找不到可行的解法，而很大部分的 NP-complete 問題都在計算機語言，程式，電路設計，統計學，程式作業上有大用，因此只好退而求其次找一個可行的近似解。很可惜的是，所有的 NP-complete 問題雖在 NP 的層次上相聯，在近似解上往往各需不同的解法，這些解法多從直觀而來，我們在此舉二個例子。
例1 在第三節問題5，包裝問題中，若採取「能裝就裝」法，即現有的盒子若可以裝得下，就不用新盒子，則此法所需用之盒子數 k1 與最可能少的盒子數 k0 滿足 。
證明 今令 n 個物品之重為 w1,w2,…,wn 公斤，因每個盒子只可以裝1公斤，故這個問題的結果是說，我們大約可以用「能裝就裝」法做得最好情形的一半好。經過較複雜的證明，Johnson 在1974年證得，當 n 很大時，
(i) ，且存在一種情形能產生。
(ii)也就是用「能裝就裝」法不會壞到 70% 以上，但可以壞到多用了 70% 的盒子。
售貨員旅行問題的一個直觀走法是先訪問最近那個尚未訪問過的城，稱為「先訪近城」法，以圖1為例，其走法為
在上面的定理中，三角不等式的條件很重要，若城之距離無此關係存在時，Sahni 與Gonzalez 在1976年證得：若 NP，則不可能存在一個有限的 m，及一個 O(nk) 計算量的走法，能使其全程長 D1 在任何 n 時滿足
未來數學家的挑戰
計算量問題 （第 6 頁）
楊照崑;楊重駿
不是所有的難題都可歸結為 NP 問題，像下得一手絕對好的圍棋現在目前的推測是比所有 NP 問題還要難的計算問題，即 NP-hard 問題，NP-hard 問題的定義如下：
定義： 若 x 為一 NP-hard 問題，則若 NP ，則 。
也就是說，即使 P=NP，x 還不一定屬於 P，但 NP, 則 x 絕不比 NP 的問題容易。在第三節中的問題1、3不一定是 NP 問題，但若能以 O(nk) 的計算量解決它們，則比較容易的問題2與4也可以 O(nk) 解決，故若問題1、3 則問題2、4，又因2、4是 NP-complete，即推出 NP=P。這與 NP-hard 之定義相合，故問題1、3均為 NP-hard 問題。同理問題5也屬於 NP-hard，不過這些 NP-hard 似乎比 NP 難不了多少，但下棋問題可能比 NP 問題要難得多，圍棋問題可以作如下觀。
問題11.（圍棋問題） 以平常的圍棋規則在一個 n x n 的棋盤上下，給定一個殘局（下了二個子就可以算殘局），首先，是否可以確定黑子在最好的下法之下，一定會贏？
這個問題不能用一般的方法證明它是不是為 NP。因為目前沒有人能猜一個必勝的下法且在 O(np) 時內證明它是對的，因為它與對方如何應付有關，而敵方的應付又與他對你以後的下法的推測有關，如此往下走，首先發生困難的是記憶上亮了紅燈，即所需要的記憶可能呈方次以上的進展。
因每一個記憶至少要用（來計算）一次，否則這個記憶就不如不要，因此一個問題的記憶若呈指數上升，則其計算量亦非呈指數似的上升不可，但若某問題只需要方次上升的記憶，即不能保證它只需要方次上升的計算量。
因此計算機學家定義三個新的集合：
PSPACE={x：x 只需要方次上升的記憶 }
註：x 均指問題。
注意在上式中 PSPACE-complete PSPACE，即 PSPACE-complete 是 PSPACE 中的難題，但 PSPACE-hard 不一定屬於 PSPACE。 Stockmeyer and Meyer 在1937年證明了一個與古克相似的定理。
若令 表示存在一個 x， 表對所有的 x，Q 表 ， 中的一個，x 為布氏變數0與1，則我們稱 f(Q1 x1,Q2 x2,…,Qn xn) 為一量化布氏公式。若 f 有可能為1，則 f 稱之為可滿足，例如把第四節中之(1)式改寫成
Stockmeyer 與 Meyer 之定理為：
定理： 檢定一個量化布氏公式為可滿足是一個 PSPACE-complete 問題。
當我們下棋面對著一盤殘局沉思的時候，我們的要求是
對我是否存在一著必勝棋可以對付
敵人任何一著應付棋
此後我是否存在一著必勝棋可以對付
敵人任何一著應付棋
……
我是否存在一著必勝棋可以對付
敵人任何一著棋
我贏了
因此這完全是 ,,,,… 之交替作用與Stockmeyer 與 Meyer 定理之關係至為密切， Robertson 與 Munro 在1918年證得圍棋是一種 PSPACE-hard 的問題，目前有人計算到圍棋 8 必勝法之記憶計算量在 10600 以上，不論人腦或電腦的記憶絕少不了一個原子，而現今所知的宇宙原子數約只有 1075。棋之道，大矣哉！要做一個下圍棋必勝的機器人是談何容易！
未來數學家的挑戰
計算量問題 （第 7 頁）
楊照崑;楊重駿
現在你明白二十世紀的大難題了，P=NP？用簡單的語言說，就是是否能找到一個只呈方次增加的方法去解決旅行、包裝、舞會等問題。平凡的問題，期待您不平凡的解答。
1. Gorey, M.R. and Johnson, D.S.《Computers and Intractability-A Guide to Theory of NP-Completeness》, 1979, Freeman and Company. 2. Pearl, J.《Hearistics-Intelligent Search Strategies for Computer Problem Solving》,1984, Addsion-Wesley. 3. Cook, S.A.〈The complexity of theorm-proving procedure〉, Proc. 3rd Ann. ACM Symp. on Theory of Computing, 1971, 151-158. 4. Jonhson, D.S. et. al.〈Worst case performance bounds for simple one-dimensional packing algorithms〉, SIAM J. Comp., 1974, 299-325. 5. Rosenkrantz, D.J. et. tl.〈An analysis of several heurishics for the traveling salesman problem〉, SIAM J. Comp., 1977, 563-581. 6. Sahin,S. and Gonzalez,〈P-complete approximation problems〉, J. ACM, 1976, 555-565. 7. Stockmeyer, L.J. and Meyer, P.R.〈Word problems requiring exponential time〉, Proc. 5th. Ann. ACM Symp. on Theory of Computing, 1973, 1-9. 8. Robertson,E. and Munro, I. 〈NP-completeness, puzzles, and games〉 Utilifas Math., 1978, 99-116.
本文地址：http://com.8s8s.com/it/it37186.htm