未來數學家的挑戰 (第 4 頁)

　1│2│3│4│5│6│7　

未來數學家的挑戰
計算量問題（第 4 頁）

楊照崑;楊重駿

首頁 | 搜尋

．原載於數學傳播十卷二期
．作者當時任教於美國佛羅里大學統計系;美國海軍研究實驗所

‧註釋
‧對外搜尋關鍵字

四、古克定律與 NP-completeness

古克定律的證明很難，就是瞭解它也不容易，我們將從幾個角度來看這個問題，試著去暸解它。它的主要結果是把前節那類問題大部歸於一個較易證明的集合，稱之為 NP，而在 NP 中找到一批互依的問題稱之為 NP-complete 類並得到下面的結果。

: 1. 若有一個 NP-complete 問題可以用 O(n^k) 計算量來解決，則全體的 NP 問題都可以用 O(n^k) 之計算量來解決，即
: 1' 若有一個 $x\in$ NP-complete且 $x\in P$ ，則 P=NP。

又換句話說，NP-complete 是 NP 中的難題，NP-complete 解決了 ⁵ ， NP 就解決了。但若有一個屬於 NP 而不屬於 NP-complete 的問題解決了，則其他的 NP 問題不一定可以解決。

什麼叫做 NP？NP 是英文 nondeterministic polynomial 的縮寫，意思就是非確定性的多項式時間。要暸解這個字。我們先看一看普通計算機的作用。

現在已知用一個計算機，要解決售貨員旅行問題非常困難，但若我們有許多計算機同時用，是否可以快到把原問題在 O(n^k) 時間內解決？「許多」，不是一、二，多一二個是於事無補的，多百個千個仍是杯水車薪，不能有很大的作用，因為就是一千個機子可以分開做，也最多只能快一千倍，在第一節內已說過，幫助不大。因此計算機學家先放眼望去，乾脆允許你可以無限的增加機器。現在我們要注意的是並不是有了無限多的機器所有的問題就可以立刻解決了，因有的問題有先後次序，例如在算下式的時候

[(a₁+a₂)a₃+a₄]a₅+a₆

除非換個形式，否則必須一步一步的解括弧，機子多了並不能加快計算的速度，而且機子多了，其間之聯絡千變萬化，一個機子要應付千千萬萬別的機子送來的信號也疲於奔命了。因此我們只假定所有的機子都只承上啟下，單線作業，不作任何橫向聯絡 ⁶ ，也就是說，機器1可以把它的結果傳給它下面的機子，像 a₁,a₂,…,a_n 而每一個機子又可以把它們的結果傳給自己的子機，但在 a₁,a₂,…,a_n 之間不互相聯絡。以售貨員旅行問題為例，若有20個城，第一個機子開始，叫下面19個機子各取一個不同的城及計算與 A 距離，而這個19個機子又將它所求得的距離交給自己的18個子機令它們取一個與自己不同的城加上距離，如此往下，在第十次時，第十階段的機子把它已取9城及總距離告訴下一個機子，叫他們再取一與已取之城不同之城加上距離，如此一直做到第19次，所有路線的距離都有了，在時間上求得所有的距離是 O(n)（但用了 19! 個計算機），古克定義凡可以在 O(n^k) 時間內用無限多計算機解決的問題為一 NP 問題。

現在要記住的是由於無橫向連絡，在所有路徑的距離都有了之後，並沒有解決售貨員問題（甲），因為不知誰是最短（若加以比較以求最短距離，則要 O(n!) 個比較），因此我們不能說售貨員旅行問題（甲）是一個 NP 問題。但上節問題2，售貨員旅行問題乙，任何一個單線都可以知道它的總距離是否不大於 B，因此每單線都有一個「Yes」或「No」的答案。只要有一個「Yes」的答案，我們即知道本問題已解決，故問題二是一個 NP 問題。在單線作業中，每個機子可以作三件事。

目前答案不明確，大家各自作業。
某線已找到答案，立刻叫停，大家停止作業，解題完畢。
此路不通，本線不再作業，但不叫停，別線仍然作業。

從上項作用，很容易看出找出答案的計算時間即某線叫停的時間，亦即任何一個有「Yes」答案線中計算量之總和，也就是說找到答案「捷徑」上所需的時間。易言之，在一非確定性計算機系統下，其子機像有「猜測」到捷徑的功能。若在任何計算步驟中，某人猜了一個答案，而計算機可以在 O(n^k) 時間內回答「Yes」或「No」，這個問題即是一個 NP 問題。再以售貨員旅行（甲）及圖1為例，若你猜一個路徑

$\begin{displaymath}A\rightarrow B\rightarrow C\rightarrow D\rightarrow E\rightarrow F\rightarrow G\rightarrow A\end{displaymath}$

我們無法知道此路是否最短，但在(B)問題中，一個「Yes」或「No」的結果只要7個加法就可以回答了。因此根據新的定義，問題2是一個 NP 問題。

由這兩個定義，讀者不難看出問題2,4,6,7,8,9（乙）與10皆為 NP 問題，特別是問題9之（甲），（乙），其實是一樣的問題，但如果你猜二個 m,n，立刻就可知道 a 是否是 mn。

古克定理的關鍵在證明若一種叫滿足問題 (Satisfactability Problem) 的例子屬於 P，則所有 NP 問題均屬於 P（即此問題屬於 NP-complete），令 $\cdot$ ,+,-（且，或，反）表三個基本的邏輯運算（即對0與1邏輯符號而言， $\bar{0}=1$ , $\bar{1}=0$ ,除了1+1=1之外，+， $\cdot$ 與一般代數之加乘相同）。令 f 為一個含有 n 個邏輯變數 (u₁,u₂,…,u_n) 的函數。假如我們可以找到一組 u₁,u₂,…,u_n，使得 f(u₁,u₂,…,u_n) = 1，則 f(u₁,u₂,…,u_n) 稱為可滿足。例如

$\begin{displaymath} f(u_1,u_2,u_3)=(u_1\cdot(\bar{u_1}+u_2)\cdot u_2+u_3)\cdot u_3 \eqno{(1)} \end{displaymath}$

為一可滿足函數，取 u₁=u₂=u₃=1 即可，但

$\begin{displaymath} f(u_1,u_2,u_3)=(\bar{u_1}\cdot u_1+u_2\cdot \bar{u_2})(u_1+u_2+u_3) \eqno{(2)} \end{displaymath}$

永為 0，故此 f 為不可滿足。

直覺上，這類問題除了將 u₁, u₂,…,u_n 一個一個以 0,1 代入檢查 2ⁿ 次之外，顯無捷徑可循，古克1971年之論文即證明這是一切 NP 問題之母。

古克定理：: 滿足問題為 NP-complete。

現在已可證明在前節中之問題，除了問題1,3,5,9 之外，全是 NP-complete 問題。

　1│2│3│4│5│6│7　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：王昱昇 ∕ 校對：陳文是 ∕ 繪圖：簡立欣

最後修改日期：6/29/2002