別傻了，目前當然無法證明 P=PSPACE 呀！就算考慮相對論也一樣！

上一篇文章中，我們開玩笑的說，考慮相對論中，空間與時間其實是同一個東西，我們得到了多項式空間就是多項式時間的結論。想當然耳，這種圖靈獎等級的事，不可能在這麼短的篇幅內搞定啊！

從根本上反駁上篇文章的論述：一個計算問題所需要的時間與空間，分別是用需要幾個步驟，以及需要多少儲存空間來衡量。如果是用理論電腦科學家最愛的圖靈機來解問題，那麼就是圖靈機需要執行多少個步驟，以及會用到紙帶上多少個格子。

「多少個」步驟、「多少個」格子，聽起來很像純量對吧！在一個慣性坐標系 \(S\) ，如果計算一個問題 \(Q\) 需要 \(T\) 個步驟、\(W\) 個格子，那在另一個慣性坐標系 \(S'\) ，計算同一個問題 \(Q\) 還是要 \(T\) 個步驟、 \(W\) 個格子啊！

那麼，接下來讓我們發揮想像力腦力激盪一下：相對論的確有說「在不同的坐標系，時間流逝的快慢不同。」儘管需要的步驟一樣多，我們有辦法利用時間流逝速度快慢不同這個事實，找到一個讓執行計算所需要的「實際時間」大幅縮短的慣性坐標系嗎？理論電腦科學家心目中的那種大幅縮短！如此一來，我們在新的坐標系做計算，就可以大幅加速了。

我們來試著講清楚所謂的「實際時間」是什麼意思。計算的過程要怎麼用物理來描述呢？想像一下計算過程的畫面。在理論電腦科學家眼中，這個畫面會是圖靈機的讀寫頭在紙帶上來回移動啦。把讀寫頭的運動畫在時空圖上，就是像下面圖中的鋸齒狀軌跡。

是的，時空圖習慣把位置畫成水平線，讓時間往上走。

在相對論中，要談所花的時間，首先要先定好「事件」。在我們想討論的問題中，很自然的會選擇開始計算、與結束計算作為兩個事件。讓我們用數學符號把話講得更清楚吧。先選好一個慣性坐標系 \(S\)。事件 1 是圖靈機開始工作，把此時的時間叫作 \(t_1\) ，讀寫頭所在的位置叫 \(x_1\)；事件 2 是圖靈機結束工作得到答案，把結束時的時間叫 \(t_2\) ，讀寫頭的位置叫 \(x_2\) 。計算所需的時間就是 \(t_2 - t_1\) ，把這個值叫作 \(T\) ；我們順便把讀寫頭結束與開始位置的距離差距 \(x_2-x_1\) 叫作 X。同樣的，換另一個慣性坐標系 \(S'\) ，我們一樣可以把事件 1 圖靈機開始的時間定義為 \(t_1'\) ，讀寫頭位置定義為 \(x_1'\) ；事件 2 圖靈機結束工作的時間定義為 \(t_2'\) ，讀寫頭的位置定義為 \(x_2'\) 。在慣性坐標系 \(S'\) 所需要的計算時間就是 \(T' :=t_2' - t_1'\) ，並且定 \(X' := x_2' - x_1'\) 。

讓我們試著把我們的目的——用相對論加速計算——寫成明確的數學問題：「已知在一個慣性坐標系 \(S\) ，計算一個問題 \(Q\) ，當問題的輸入大小為 \(n\) ， 需要時間 \(T(n)\)、讀寫頭在結束與開始的距離是 \(X(n)\) 。我們的目的是要找到另一個坐標系 \(S'\) ，使得在這個坐標系 \(S'\) 下，圖靈機從開始到結束工作所需的時間 \(T'(n)\) 越短越好。」

這邊也順便講一下上篇文章賴皮的地方：上篇文章裡說「某個問題可以在 \(p(n)\) 的時間內解決，轉換成另一個坐標系就是可以使用 \(p(n)\) 的空間解掉。」我們要證明這樣的「另一個坐標系」真的存在才能做出這般的結論啊！所以，接下來我們要做的事就是試著找出這樣的坐標系。劇透：找不到。

我們想試著加速 PSPACE 的問題。在 PSPACE 裡的問題，所使用的格子數量是少的，但總共需要花的時間可能是很多的。讀寫頭開始工作與結束工作時的距離，當然會比總共用到的格子還要小。所以， PSPACE 問題會是 \(X\) 小，但 \(T\) 大。

小是多小大是多大呢？ PSPACE 使用的格子的數量最多只會有多項式級別那麼多個格子，於是我們有 \(X \le \operatorname{poly}(n)\) 。所需時間的話，以人類目前的知識， PSPACE 問題中最好的時間上限是指數多的時間，所以我們讓 \(T=\operatorname{exp}(n)\) ，才保證能算出每個 PSPACE 問題 (嚴謹一點來說是 2^\operatorname{poly}(n))。接下來，我們要做的事就是：已知在慣性坐標系 \(S\) 下，事件 1 與事件 2 位置差距是 \(X \le \operatorname{poly}(n)\) ，時間差距是 \(T=\operatorname{exp}(n)\) ，找到另一個慣性坐標系 \(S'\) ，讓這個坐標系中兩事件的時間差距 \(T'\) 越小越好。

這個坐標 \(S'\) 會是什麼呢？事件 1 與事件 2 是讀寫頭在時空中移動軌跡的兩個端點，所以顯然兩事件有因果關係；或者也可以這樣看，這兩個事件標示圖靈機進行計算的開始與結束，當然開始會影響結束。總之，兩事件有因果關係，屬於類時（ time-like ）的關係。使得兩個類時事件的時間間隔最短的坐標系，是能讓兩事件在同一個位置的坐標系。這個最短的時間間隔就是兩事件的原時（ proper time ）。

我們要找的那個慣性坐標系 \(S'\) 會讓事件 1 與事件 2 在相同位置。換句話說，在慣性坐標系 \(S\) 下看，圖靈機開始工作 \(t_1\) 時， \(S'\) 的原點在讀寫頭的位置 \(x_1\) ；圖靈機結束工作 \(t_2\) 時， \(S'\) 的原點在 \(x_2\)。意即， \(S'\) 相對 \(S\) 以 \(X/T\) 的速度移動。有就是下圖中的紅色箭頭。補充一點，雖然在 \(S'\) 下看，開始與結束讀寫頭在同一個位置，但同時紙帶也是會相對 \(S'\) 移動，所以停止工作時，讀寫頭還是停在與 \(S\) 下看到的格子一樣。

我們剛才說， \(X\le \operatorname{poly}(n)\) ，以及 \(T = \operatorname{exp}(n)\) 。所以 \(S'\) 的速度 \(X/T\) 非常小，只有指數級別的小。也就是說， \(S'\) 速度很慢，所以時間膨脹不明顯， \(T'\) 其實跟 \(T\) 是同一個量級的！上篇文章證明失敗！

做個結論吧：我們用相對論本身反駁了利用相對論加速計算問題的想法。

主題標籤： 相對論 計算理論 愚人節