楊照崑;楊重駿

一、前言 二、計算量 三、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，所有的城，一個可行的方法是

由於電子計算機的發展，有許多以前認為枉費時的計算，像行列式之值，反矩陣，高次方程式的解，都可以在極短的時間內解決。但也突然出現了一些新問題，連大型計算機也望之興嘆。像售貨員問題，因為找不到比硬排好得很多的做法，使得數學家們開始想要證明，根本找不到比硬排好得很多的做法。這個證明至今尚未找到。就像以前一角三等分問題一樣，既然找了幾千年找不到用圓規直尺三等分任一角的方法，也許我們可以證明絕對不可能用圓規直尺三等分一角。 現在我們要證明絕不可能寫一個計算機程式大大的簡化售貨員旅行問題。與三等分一角問題不同的是，前者是一種數學上的好奇，而當今的問題與實際用途卻有密切的關連。

在此我們一直強調一個好得很多的方法。原因是對這類的問題，你若能計算快一倍或十倍、千倍，往往起不了什麼大作用，好像剛才的二十城旅行問題，即使快了千倍，仍需三年的計算時間，而再加三城立刻就把這個計算法的效果抵消了，因此我們所要的是計算量基本層次的減少，這就是我們在下一節所要討論的。