未來數學家的挑戰 楊照崑;楊重駿
|
.原載於數學傳播十卷二期 .作者當時任教於美國佛羅里大學統計系;美國海軍研究實驗所 •註釋 •對外搜尋關鍵字 |
不是所有的難題都可歸結為 NP 問題,像下得一手絕對好的圍棋現在目前的推測是比所有 NP 問題還要難的計算問題,即 NP-hard 問題,NP-hard 問題的定義如下:
也就是說,即使 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 問題要難得多,圍棋問題可以作如下觀。
這個問題不能用一般的方法證明它是不是為 NP。 因為目前沒有人能猜一個必勝的下法且在 O(np) 時內證明它是對的,因為它與對方如何應付有關,而敵方的應付又與他對你以後的下法的推測有關,如此往下走,首先發生困難的是記憶上亮了紅燈,即所需要的記憶可能呈方次以上的進展。 因每一個記憶至少要用(來計算)一次,否則這個記憶就不如不要,因此一個問題的記憶若呈指數上升,則其計算量亦非呈指數似的上升不可,但若某問題只需要方次上升的記憶,即不能保證它只需要方次上升的計算量。 因此計算機學家定義三個新的集合:
注意在上式中 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)式改寫成
則上式不可能滿足,因對 (u3 為 0 或 1)而言,f 不全是1。 Stockmeyer 與 Meyer 之定理為:
當我們下棋面對著一盤殘局沉思的時候,我們的要求是
對我是否存在一著必勝棋可以對付 因此這完全是 ,,,,… 之交替作用與Stockmeyer 與 Meyer 定理之關係至為密切, Robertson 與 Munro 在1918年證得圍棋是一種 PSPACE-hard 的問題, 目前有人計算到圍棋 8 必勝法之記憶計算量在 10600 以上,不論人腦或電腦的記憶絕少不了一個原子, 而現今所知的宇宙原子數約只有 1075。棋之道,大矣哉!要做一個下圍棋必勝的機器人是談何容易!
|
|
(若有指正、疑問……,可以在此 留言 或 寫信 給我們。) |
EpisteMath (c) 2000 中央研究院數學所、台大數學系 各網頁文章內容之著作權為原著作人所有 |
編輯:王昱昇 / 校對:陳文是 / 繪圖:簡立欣 | 最後修改日期:6/29/2002 |