未來數學家的挑戰【六、NP-hardness 與圍棋】

六、NP-hardness 與圍棋

不是所有的難題都可歸結為 NP 問題，像下得一手絕對好的圍棋現在目前的推測是比所有 NP 問題還要難的計算問題，即 NP-hard 問題，NP-hard 問題的定義如下：

定義： 若 x 為一 NP-hard 問題，則若 NP ，則 。

也就是說，即使 P=NP，x 還不一定屬於 P，但 NP, 則 x 絕不比 NP 的問題容易。在第三節中的問題1、3不一定是 NP 問題，但若能以 O(n^k) 的計算量解決它們，則比較容易的問題2與4也可以 O(n^k) 解決， 故若問題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(n^p) 時內證明它是對的，因為它與對方如何應付有關，而敵方的應付又與他對你以後的下法的推測有關，如此往下走，首先發生困難的是記憶上亮了紅燈，即所需要的記憶可能呈方次以上的進展。

因每一個記憶至少要用（來計算）一次，否則這個記憶就不如不要，因此一個問題的記憶若呈指數上升，則其計算量亦非呈指數似的上升不可，但若某問題只需要方次上升的記憶，即不能保證它只需要方次上升的計算量。

因此計算機學家定義三個新的集合：

PSPACE={x：x 只需要方次上升的記憶 }
註：x 均指問題。

PSPACE-complete：

若 PSPACE,

又 PSPACE-complete,

且 ,

則 P= PSPACE。

PSPACE-hard：

若 PSPACE-hard,

且 ,

則 P= PSPACE。

注意在上式中 PSPACE-complete PSPACE，即 PSPACE-complete 是 PSPACE 中的難題，但 PSPACE-hard 不一定屬於 PSPACE。 Stockmeyer and Meyer 在1937年證明了一個與古克相似的定理。

若令 表示存在一個 x， 表對所有的 x，Q 表 ， 中的一個，x 為布氏變數0與1，則我們稱 f(Q₁ x₁,Q₂ x₂,…,Q_n x_n) 為一量化布氏公式。若 f 有可能為1，則 f 稱之為可滿足，例如把第四節中之(1)式改寫成

則上式不可能滿足，因對 （u₃ 為 0 或 1）而言，f 不全是1。

Stockmeyer 與 Meyer 之定理為：

定理：

檢定一個量化布氏公式為可滿足是一個 PSPACE-complete 問題。

當我們下棋面對著一盤殘局沉思的時候，我們的要求是

對我是否存在一著必勝棋可以對付
敵人任何一著應付棋
此後我是否存在一著必勝棋可以對付
敵人任何一著應付棋
……
我是否存在一著必勝棋可以對付
敵人任何一著棋
我贏了

因此這完全是 ,,,,… 之交替作用與Stockmeyer 與 Meyer 定理之關係至為密切， Robertson 與 Munro 在1918年證得圍棋是一種 PSPACE-hard 的問題， 目前有人計算到圍棋 ⁸ 必勝法之記憶計算量在 10⁶⁰⁰ 以上，不論人腦或電腦的記憶絕少不了一個原子， 而現今所知的宇宙原子數約只有 10⁷⁵。棋之道，大矣哉！要做一個下圍棋必勝的機器人是談何容易！