從時間階梯走到空間階梯
在前兩篇導覽裡，你換掉了你的量尺。你不再數時鐘的滴答，而是數一台圖靈機在格子上塗寫的數量。讓這件事誠實的訣竅，是工作帶慣例：輸入放在它自己那條唯讀的帶子上、不向你收費，你只為那條你真正寫入的、獨立的工作帶付錢。正是這道分隔，讓 L 與 NL 有了意義——一台機器能讀進龐大的輸入，卻只保留一塊對數大小的草稿紙。如今我們把錢包大大張開，問道：若你被允許使用一條長度是輸入大小之任意多項式的工作帶，你能判定什麼？
那個類就是 PSPACE：所有能被一台確定性圖靈機用 O(n^k) 個工作帶格子判定的問題（k 為某個固定常數，n 為輸入大小）。注意我們沒有限制的是——時間。一台只有多項式量記憶體的機器可以跑上極久：它最多能造訪約 2^(多項式) 個相異的記憶體配置，之後它要嘛重複某個配置（於是陷入循環）、要嘛停機。所以 PSPACE 對思考時間很大方，卻對你任一瞬間能裝在腦中的量很嚴格。光是「什麼東西稀缺」這一個轉變，竟捕捉到一種風味截然不同的問題。
PSPACE 在地圖上的位置
讓我們把 PSPACE 釘在你已熟悉的那些類之間。首先，NP 在 PSPACE 之內。一個 NP 問題有一份你能快速檢查的簡短憑證；要在多項式空間內判定它，你只需逐一輪過每一個候選憑證、跑那個多項式時間的驗證器，並為每次試驗重用同一塊草稿空間。你可能要試指數多份憑證——沒關係，這裡時間免費——但每次試驗只需多項式記憶體，所以整個搜尋都裝得進 PSPACE。依同樣的道理，co-NP 也住在 PSPACE 之內：只要把條件從「某一份憑證成功」改成「全部憑證都失敗」即可。
反方向看，PSPACE 在 EXPTIME 之內，也就是能在指數時間內解的問題。論證就是剛才那個配置計數：一台用多項式空間的機器只有 2^(多項式) 種可能配置，若它從不重複任何一個，就必定在那麼多步之內停機——這是個指數時間上界。把我們在整座階梯上蒐集到的一切疊起來，得到一條乾淨的鏈：L 在 NL 之內、NL 在 P 之內、P 在 NP 之內、NP 在 PSPACE 之內、PSPACE 在 EXPTIME 之內。每一類都被下一類包含；這部分是穩固的定理，不是猜想。
招牌問題：量化布林公式
每個類都有它代表性的難題。對 NP 來說那是可滿足性：存在一個指派使某布林公式為真嗎？這單一的存在性問句——「有沒有辦法？」——正是一個驗證器拿來核對所猜憑證的東西。PSPACE 的代表則把旋鈕轉到底。一個量化布林公式（QBF）讓你把兩種量詞都擺到變數前面，順序任意：「對所有 x，存在 y，對所有 z，……」後接一個普通的布林公式。問題是：整個被量化的句子算不算真。
為什麼加上全稱量詞會把難度炸得這麼戲劇化？單純的 SAT 只問存在，一次幸運的猜測就解決了。但「對所有 x」逼你為 x 的每一個值都確認某件事——你沒法靠運氣；實際上你必須把 x = 真與 x = 假兩條分支都檢查過、且兩邊都成立。而這些又與「存在」交替出現，後者只需一條分支成立即可。要算出公式的值，你得遞迴：剝掉最外層的量詞、試它那變數的兩個值，並在每次嘗試之內再剝掉下一個量詞。這棵遞迴樹寬達指數級，但是——這正是 PSPACE 的魔法——你任一時刻只走一條從根到葉的路徑，回溯時還重用同一批堆疊框架。那遞迴的深度不過是變數的個數，所以你握住的記憶體只是多項式的。
QBF: forall x. exists y. (x OR y) AND (NOT x OR NOT y)
Evaluate by recursion (one path live at a time, reuse the frame):
x = FALSE : exists y. (F OR y) AND (T OR ...)
y = TRUE -> (F OR T)=T AND (T)=T -> TRUE [y found]
x = TRUE : exists y. (T OR y) AND (F OR NOT y)
y = FALSE -> (T) AND (F OR T)=T -> TRUE [y found]
forall x needs BOTH x-branches true: TRUE and TRUE -> whole QBF = TRUE
Depth of recursion = number of variables -> memory is polynomial.
Width of the tree = 2^(variables) -> time is exponential.QBF 之於 PSPACE，正如 SAT 之於 NP：它是 PSPACE 完全的。意思是 QBF 在 PSPACE 之內（上面那個遞迴就是那個多項式空間演算法），而且 PSPACE 中的每一個問題都在多項式時間內歸約到它。所以 QBF 名列 PSPACE 裡最難的問題之中，而身為 PSPACE 完全問題，它在此扮演的錨點角色，正如 SAT 之於 NP——一個整個類都能被翻譯進去的單一難題。事實上，單純的 SAT 恰好就是 QBF 的特例：當每一個量詞都剛好是「存在」時。這正是一種俐落的方式，看出 NP 如何巢居於 PSPACE 之內。
為什麼 QBF 其實是一場賽局
這裡有個能讓你感受到 PSPACE 完全性含義的生動方式：一個量化公式，是用邏輯寫成的雙人賽局。把「存在 y」讀成一位我們稱為「證明者」的玩家所下的一步，他試圖讓公式為真；把「對所有 x」讀成「對手」所下的一步，他試圖讓公式為假。量詞的順序，就是出手的順序。「對所有 x，存在 y，……」這句話的字面意思就是：無論對手在 x 下了什麼，證明者都有一招回應 y，如此一路下去。整個 QBF 為真，恰恰當證明者擁有一個必勝策略——一套能回應每一種可能攻擊的方法。
這正是為什麼，許多真實的雙人棋類遊戲，一旦你把它推廣到 n×n 的棋盤，就是 PSPACE 完全（或近乎如此）的：推廣版的 Geography、推廣版的 Hex，以及許多其他遊戲。「先手方從這個局面有沒有一個必勝走法？」這正是 QBF 所提出的、那個交替的「對所有／存在」問題——我有一步（存在），使得對你的每一種回應（對所有），我仍有一步，如此繼續。判定誰會贏，意味著探索那棵賽局樹，而那棵賽局樹，恰恰就是我們剛畫的那棵遞迴樹，一次只走一條路、用一個多項式深的堆疊走完。
不過，對「賽局都是 PSPACE 完全」這句口號要小心。它成立的前提是完全資訊、走步數有多項式上界的雙人賽局，且推廣到任意棋盤大小。標準的 8×8 西洋棋與 19×19 圍棋是有限的物件——固定大小的棋盤只有有限多個局面——所以照字面講，它們甚至談不上有意義地落在某個複雜度類裡；複雜度需要一個會成長的輸入。那些 PSPACE 結果說的是 n×n 的家族。而那些對局可以跑指數步長的賽局（某些西洋棋推廣版）會爬過 PSPACE、進入 EXPTIME——乾淨的 PSPACE 故事，需要走步數保持為多項式。
在 NP 之上：多項式階層與前方一瞥
QBF 還順手給你一條自然的路，把 NP 與 PSPACE 之間的落差分級地一階一階爬上去。NP 是只有單一一段「存在」量詞的公式；co-NP 是單一一段「對所有」。那麼若恰好允許兩次交替——「存在……對所有……」呢？或三次？每一個固定的交替次數定義出一層，而這整座層塔就是多項式階層。它的第一層是 NP 與 co-NP；更高的樓層允許更多次量詞切換。具有無上界交替次數的 QBF，坐落在整座塔之上，這正是它何以能捕捉整個 PSPACE、而非任何單一樓層的原因。
一個值得弄對的微妙之處：co-NP 不是「不在 NP 裡的問題」。「co」意思是補集——你把「是」與「否」對調。經典的 NP 問題是「這個公式可滿足嗎？」；它的 co-NP 雙生問題是「這個公式不可滿足嗎？」，也就是「它對所有指派都保持為假嗎？」。NP 與 co-NP 究竟是不是不同的類，是又一個著名的未解問題；我們相信它們不同（多數專家懷疑不可滿足性會有簡短憑證），但沒人證明過。倘若 NP 結果等於 co-NP，整座多項式階層就會塌縮到它的第一層。
最後一個驚奇，用來鋪陳下一篇。我們是用一台確定性機器定義 PSPACE 的。那麼，若我們讓機器是非確定性的、但空間仍封頂在多項式——叫它 NPSPACE——會如何？令人吃驚的是，Savitch 定理證明了 PSPACE 等於 NPSPACE：對於空間，非確定性買不到比一個平方級擠壓更多的東西（任何用空間 s 的非確定性計算，都能用 s 的平方的空間確定性地模擬）。這與時間的世界天差地遠——在那裡我們懷疑 P 離 NP 非常遠。下一篇會拆解 Savitch 那個巧妙地把一個可達性問題遞迴對半切的手法是如何辦到的——還有一個相伴的驚奇，Immerman-Szelepcsenyi，它證明了 NL 甚至等於它自己的補類 co-NL。