未來數學家的挑戰

http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/index.html
未來數學家的挑戰
計算量問題

楊照崑;楊重駿

一、前言

有數學家說過「一個好的問題勝過十個好解答」。 因為解答一出，此問題已是到了終點，對不斷求創新的人們而言，已不構成挑戰。 而新的問題是源頭活水，能開拓新的境界。多數人都不願沉醉在好的解答中不斷的玩味，而希望找到新的問題，不斷的思考，摸索。

大家在《數播》上已看見了不少好的問題，尤其最近康明昌教授談到的費馬定理，幾何三大難題，都是極有趣的問題。 有的已有了解答，有的尚待解決。 除了上面的題目外，像四色問題（即任何一個地圖只要用四種顏色就可以把國界分開），五次以上方程式的公式解，及數論上質數分佈問題，都曾在職業及業餘數學家的心目中佔有相當的地位。 本文所要介紹的是一個最近（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，所有的城，一個可行的方法是

問題是：這是否是最短的途徑？也許

更近呢？加起來的結果第一路徑總長235里，而第二路徑總長為230里，故第二路徑較短， 但是否存在一個更短的路徑呢？目前的方法接近一個一個的排著試，還沒有找到更好可以尋得最短路徑的方法。對七個城而言，共有 6!=720 個排法，尚不算難，但若有 20 個城，則排法就有 19! 種。因

故

在排列組合裡 n! 寫起來輕鬆，但 1.21 x 10¹⁷ 是一個大得不得了的數字，若每秒鐘排一次，要排 3.84 x 10⁹ 年（一年約為 3.15 x 10⁷ 秒）， 即使使用計算機，每秒排一百萬次（不容易做到）也得重做三千年才能找到答案。「生也有涯，知也無涯」，想不到區區二十個城，要三十個世紀才能找到答案。

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

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