動機
Savitch 定理告訴我們非確定性空間如何能由確定性機器模擬,但它並沒有說明給予確定性機器更多記憶體是否會令其能力更強。空間層級定理在一項可構造性假設下回答了這個問題。其對角化機器在一個經仔細選定的中間記憶體預算內模擬一個候選機器,等待足夠長的時間以偵測重複出現的組態,然後與該候選機器作出相反的判定。
關鍵的比較是漸近意義上的。一個程式具有固定的描述及固定的模擬常數,而兩個空間界限之間的比值卻可以無限增長。組態的編碼與計數至關重要:一個等待任意機器停機的模擬,本身並不是一個判定器。
定義 3.7.1
(空間界限與空間可構造性)
我們使用具有唯讀輸入帶及有界工作帶的確定性機器。工作空間界限計算的是被訪問過的工作格,而不包括唯讀輸入。若存在一部確定性機器,對於長度為 的輸入,能以 空間構造並標記恰好 個工作格,則稱函數 在此處為空間可構造。我們假設對於足夠大的 皆有 ,使機器能儲存輸入磁頭位置及基本計數器。更改界限的有限多個值,不會影響所得的漸近空間類。
為何空間界限可充當時鐘
定理 3.7.2
(組態數目界限)
固定一部具有有限工作字母表的確定性機器 。在長度為 的輸入上,若 至多使用 個工作格,則其可能組態的數目至多為 ,其中 是依賴於 但不依賴於 或 的常數。若某個計算重複出現同一組態,則其此後永不停機。
證明
(計算組態數與鴿巢步驟)
一個組態記錄有限控制狀態、已訪問工作視窗的內容、工作磁頭位置以及輸入磁頭位置。大小為 的工作字母表給出至多 種可能的視窗內容;磁頭位置分別貢獻至多 及 的因子,而狀態集合是固定的。對於適當的 ,其乘積至多為所示的二的冪,對於較小的 ,可藉增大 而涵蓋。
確定性的下一步規則使相等的組態產生相同的後續計算。若某組態在停機前重複出現,則其兩次出現之間的片段會永遠重複,因此該計算此後不可能停機。故此,一個具有組態數目有效界限的模擬,可在超過該數目的步數後安全地宣告不停機。
例題 3.7.3
(一個小型的有限狀態空間)
假設一部機器有兩個控制狀態、一條限制為三格的二進位工作帶、四個可能的工作磁頭位置及六個輸入磁頭位置。可能的組態至多有 個。若一個確定性計算在觀察了 385 個組態後仍未停機,則它已重複了某一組態。此有限例子說明了鴿巢原理的論證;層級定理的證明需要的是隨輸入長度增長時的一般界限,且在整個模擬過程中須一致地處理機器的描述。
常見錯誤
(大的時鐘不需要大的帶)
一個計數至 的計數器只使用 個位元,儘管計數至該值可能需要指數時間。層級論證是空間證明,而不是多項式時間的模擬。其龐大的時鐘與所聲稱的記憶體界限是相容的。
概念視角結構
組態構成每點只有一個出口的圖
把確定性機器在固定輸入上的組態當作頂點,每個組態指向它的後繼組態。每個頂點至多有一條出邊,而一次計算就是從起始頂點出發的路徑。路徑恰在到達停機頂點時停機;若重訪某個頂點,就是落入迴圈,永遠不會停機。因此時鐘只需數到頂點的總數。
模擬一部被描述的機器
我們使用一個標準的通用直譯器,配合固定的有限機器編碼。其轉移表是從唯讀輸入中讀取,而不是整份複製到工作帶上。對於一部固定的被描述機器 ,模擬其 個工作格至多需要 個直譯器工作格,其中 是依賴於 及其字母表的常數。直譯器可以追蹤被描述機器的狀態及磁頭位置,在需要轉移時掃描其描述,並計算被模擬的工作格數目。額外的掃描可能耗費時間;我們不聲稱任何時間界限。通常的有限字母表編碼及通用模擬在此作為背景假設。
對於對角化構造,我們還需要直譯器自身的一個一致的組態時鐘。我們把被編碼的機器描述限制為至多 個輸入位元,並把直譯器的工作視窗上限定為 格。直譯器是一部固定的機器,因此其自身的組態至多有 種可能,其中 為某個固定常數。該描述已是固定輸入的一部分,不是其組態中另一個會變化的成分。時鐘有 個位元。
例題 3.7.4
(固定的程式,增長的填充)
一個編碼可以由 的自定界描述,後接若干個零組成。對於每個固定的 ,描述長度是常數。藉著充分的填充,它會變得至多為 ,而被模擬的輸入仍是整個填充後的字串。因此,限制描述長度並不會把任何固定的候選機器從所有足夠長的對角化輸入中排除。
在兩個界限之間選取預算
設 為空間可構造函數,最終皆至少為 ,且 。定義
則 且 。取上整函數並不改變這兩個極限。特別地,最終有 。對角化機器可以使用 工作空間計算出足夠精確的整數 :構造兩個界限,以二進位表示其數值,相乘並取整數平方根。由於 ,對於足夠大的 ,此界限已包括構造 所需的工作量。對於有限多個較短的輸入,機器可以採用任何固定的後備行為。
定理 3.7.5
(確定性空間層級)
在所述假設下,
證明
(對每個固定的小空間機器作對角化)
對於長度為 的輸入 ,對角化機器首先嘗試解析出一個長度至多為 的有效自定界確定性機器描述。若輸入中不存在這樣的描述,則拒絕。否則,它計算 ,分配一個 格的直譯器工作視窗,並在同一個完整輸入 上模擬被描述的機器 。若直譯器試圖離開其視窗,則對角化機器拒絕。它同時維持上述的一致組態時鐘。若時鐘在模擬停機前到期,則拒絕。若被模擬的機器接受,則對角化機器拒絕;若其拒絕,則對角化機器接受。
此構造必定停機:視窗違規、被模擬機器停機或有限的時鐘,都會結束運行。構造 耗費 空間;模擬及其時鐘耗費 空間。因此所得的語言 屬於 。
假設為了導出矛盾,存在一部固定的判定器 ,對於所有足夠大的 ,以至多 個工作格判定 。取編碼 且長度趨向無限的填充輸入 。最終,描述長度的限制會被滿足。對於這部固定的 ,通用直譯器所用空間至多為 ,由於 且 ,對於所有足夠大的此類長度,該值小於 。因此視窗不會溢出。被模擬的判定器停機,而時鐘也足夠長:否則,有界確定性直譯器的某個組態會重複,而模擬此後就不可能停機。對角化機器於是輸出與 相反的結果,與 判定 的假設矛盾。故 。
由於最終有 ,通常的包含關係隨之成立。嚴格性的證明在吸收模擬常數時,需要的是單一固定的候選機器;它並不假設同一個常數對每個被編碼的程式都同樣適用。
證明透視
各項假設在對角化論證中的位置
這個論證分成兩半,量詞並不相同。上界對每個輸入都成立:機器停機並使用 空間,這需要可構造性(用來建立 )、(使 ),以及由同一部固定直譯器、同一個常數 給出的統一時鐘。下界只涉及單一的候選機器 ,其常數 在 增大之前已經固定。不顯然的一步是填充:對角化機器從輸入中讀取 的描述,補上零使固定的 出現在無窮多個輸入上,所以描述長度的上限不會排除任何候選機器。假設 在下界中恰好用一次,即 ,使視窗最終超過 。若 ,這一步就失效: 只約為 ,視窗可能溢出,對角化機器便在沒有與 作出相反判定的情況下拒絕,不會產生矛盾。
例題 3.7.6
(對數空間與對數平方空間)
取 及 。兩者皆為空間可構造,且 。定理給出一個可在 空間內判定、但不能在 空間內判定的語言。該證明是透過對角化判定器而得的存在性證明;它並沒有指出具有此性質的某個熟悉的完全問題。
反例模式
常數倍數永遠不能分離空間類
一個誘人的說法是:當 時,層級定理仍給出 ,因為較大的界容許十倍的記憶體。取 及 。此時 並不趨向零,假設不成立,結論亦不成立。若機器 以至多 個工作格判定某語言,便構造 :其工作字母表由 的十個符號組成的區塊構成,區塊內的位置由有限控制記住。於是 逐步模擬 ,至多使用 個區塊格,並判定同一個語言。因此即使對精確的界,也有 ;嚴格分離需要小 o 的差距 。
一個推論,以及對時鐘的進一步審視
推論 3.7.7
(PSPACE 內部的嚴格包含)
。
證明
(對數平方空間的見證語言)
對數平方的例子提供了一個屬於 、但不屬於 的語言。由於 以 的某個多項式為上界,此語言屬於 PSPACE。每部對數空間機器同樣使用多項式空間,故 ;所構造的語言使此包含關係成為嚴格。這個結論使用的是確定性空間層級定理,並沒有解決 P 與 PSPACE 之間的關係。
例題 3.7.8
(指數時鐘所用的空間)
假設有界直譯器至多有 個可能的組態。從零計數至 需要 101 個二進位位元,另加常數量的控制空間。如此大小的計數器可以與直譯器視窗一併維持;在空間類的論證中,容許其運行時間可能極其龐大。若對判定器的模擬一直停留在其視窗之內,它必定在組態重複之前停機,因此這個時鐘不會錯誤地令它超時。
該時鐘所界定的是有界直譯器的組態,而不僅僅是被模擬機器那帶有依賴於程式的字母表的組態。這個選擇在對角化構造中產生單一的一致常數。反過來,為了證明任何固定的小空間候選機器皆能容納於直譯器視窗之內,證明可以使用依賴於該單一候選機器的常數。若將這兩個量詞混為一談,對角化判定器就會缺乏一致的界限。
此定理比較了甚麼,又沒有比較甚麼
此定理論及的是確定性空間類與語言。它既沒有說明較大類中的每個語言對較小類都是困難的,也沒有證明如 P 對 PSPACE 這類的分離。它所產生的,是差集中的一個語言。它亦沒有建立非確定性空間層級,後者需要另行論證。
空間可構造性並非裝飾:對角化機器必須分配並監察由所指名函數導出的預算。若沒有對這些界限的某種有效取用方式,上述構造便沒有根據。假設 是為了支付對唯讀輸入作索引及模擬器計數器的開銷;次對數模型則需要額外的小心處理。
具有相同間距的非確定性層級成立,但對角化機器現在必須取答案的補。
自然延伸的下一個問題
同樣的間距能分離非確定性空間嗎?
具有相同間距的非確定性層級成立,但對角化機器現在必須取答案的補。
具有相同小 o 間距的非確定性空間層級同樣成立。上面確定性的證明把被模擬機器的答案反轉,而對非確定性機器來說,這等於要在可用空間內判定其語言的補集。因此非確定性的情況需要另一個論證,非確定性空間的補集結果就是相關的工具。
練習與解答
快速檢查
(為何指數長度的時鐘可以放進其指數的線性空間之內?)
數一數時鐘所達到的最大數需要多少位元。
解答 · 答案
計數至 的二進位計數器只需 個位元,儘管它可能執行指數次數的遞增。
快速檢查
(若確定性組態在機器停機前重複出現,會有甚麼問題?)
比較每次出現之後的後續計算。
解答 · 答案
確定性使相同的未來重複出現,因此機器會永遠循環,此後不可能停機。
快速檢查
(為何對角化機器是在整個填充後的輸入上,而不是只在其描述上模擬被描述的程式?)
候選機器必須判定哪一個輸入?
解答 · 答案
該假定的候選機器在完整輸入上判定對角化語言。正是在同一輸入上的不一致,導出了矛盾。
快速檢查
(為何 最終大於 的每個固定倍數?)
用一個平方根給 一個下界。
解答 · 答案
由於 且 ,該比值趨向無限。
快速檢查
(空間可構造性假設用於何處?)
想一想對角化機器在模擬之前須先計算甚麼。
解答 · 答案
它使對角化算法能在較大的空間容許量之內,構造並監察其隨輸入長度而定的記憶體預算。
快速檢查
(該證明是否蘊含 嚴格小於 ?)
檢查常數倍數是否滿足小 o 假設。
解答 · 答案
不蘊含。常數倍數不滿足所需的小 o 關係,而上述區塊打包的論證表明這兩個類相等。
快速檢查
(此定理是否證明了 P 不等於 PSPACE?)
它到底分離了甚麼?
解答 · 答案
不能。該定理分離的是適當的確定性空間界限;它並沒有把所有多項式時間語言與 PSPACE 作比較。
快速檢查
(為何即使層級定理的證明沒有指出差集中某個熟悉的自然語言,仍可得出 ?)
見證語言是否必須是標準問題?
解答 · 答案
它在 中構造了一個不屬於 的特定對角化語言。較大的類包含於 PSPACE 之內,因此即使我們不能把該語言辨認為標準的圖問題,所構造的語言仍可見證嚴格性。