動機
上一節的確定性可達性算法在每層遞歸中只保存兩個端點及一個候選中點。對於有 個頂點的圖,它使用 空間。一部使用 空間的機器大約有 個組態。代入 ,便得到 的模擬空間這一猜想。
但代入公式還不是證明:如果先把整個組態圖寫出來,可能已經用掉指數空間。我們必須在不儲存圖的情況下產生頂點名稱、枚舉中點和檢查鄰接關係,還要說明模擬器如何得知空間界限、遞歸為何停機,以及為何不會漏掉接受計算。這些細節正是一般定理的核心。
定義與機器約定
所有對數以 為底。輸入長度為 ,容許 。機器有一條帶端點標記的雙向唯讀輸入帶,以及固定有限條工作帶;狀態集、字母表和工作帶數目都不隨 改變。空間只計算訪問過的工作儲存格,不計算輸入帶。改用單條工作帶只影響下文界限的常數因子,所以用單向無限工作帶描述組態即可。
定義 3.2.1
(空間類與可計算的空間界限)
與 分別由能以 工作空間判定的語言組成,前者使用確定性機器,後者使用非確定性機器。非確定性判定器的每條分支都停機,且恰在至少一條分支接受時接受。這裏採用一個方便的空間可構造性假設: 取整數值,,並且有確定性程序在輸入 上,以 空間算出 的二進制表示,且劃定含 個儲存格的工作區域。
這一明確假設足以證明標準的空間可構造版本。常見界限如 、它的平方及 的正整數次冪均滿足它。模擬器不必真的保存 :只需保存虛擬讀頭位置,判斷它是否位於 ,便能模擬一元輸入。額外的 位元已包括在 預算內。
固定一部判定某個 語言的機器 。選取足夠大的整數常數 ,使每條分支最多使用 個工作儲存格。一個組態記錄狀態、輸入讀頭位置、工作讀寫頭位置及全部 個工作符號,包括未使用的空白。給定 後,各欄位的長度固定。若狀態集為 、工作字母表為 ,組態元組數至多為
除固定數目的分隔位元外,每個元組可用
位元編碼。各項都為 ,特別是輸入讀頭欄位由 控制,而工作讀寫頭欄位滿足 。
不必儲存的圖
選定公共標籤長度 ,足以編碼全部組態和一個額外目標 。例如,在每個元組前加 ,用一個以 開頭的標籤表示 ,其餘不能解碼的標籤均視為無效。把全部 個標籤視為頂點,無效標籤是孤立點。若 的一步合法轉移在 儲存格窗口內把 變為 ,就有邊 ;若 是接受組態,就加邊 。目標 沒有出邊。真實初始組態的標籤記為 。
命題 3.2.2
(隱式組態圖)
該圖的邊謂詞可在 工作空間內判定。並且, 接受 ,當且僅當從 可達 。
證明
(證明)
給定兩個標籤,先檢查它們的欄位是否表示組態或指定目標。對於組態間的邊,查閱固定轉移表,掃描真實輸入以讀取第一個標籤所指定的輸入符號,檢查狀態變化、允許的讀寫頭移動和所寫符號,並逐項確認其餘工作符號未變。固定數目的標籤和掃描計數器共需 空間。檢查接受組態到目標的邊更簡單。其餘情況一律拒絕,包括離開工作窗口的移動。
接受計算沿合法組態走到接受組態,再走一步便到達 。反過來,到達 的通路最後一步必來自接受組態。從真實初始組態出發,沿邊歸納可知前面每一步都屬於 的合法計算。無效標籤沒有相鄰邊,不能製造虛假的接受通路。真實空間界限又保證刪除窗口外轉移不會刪除任何從 出發的計算。
我們枚舉的是所有標籤,而不是僅僅枚舉可達組態。後者本身就需要解決可達性,若把它作為建圖的前提,論證便會循環。語法有效性容易檢查;從初始組態能否到達,則交給下面的搜尋。
定理與證明
定理 3.2.3
(Savitch 定理)
在上述空間可構造性及下界假設下,
模擬器是確定性的,並在每個輸入上停機。
證明
(透過有界中點搜尋證明)
對於標籤 和整數 ,用 表示存在從 到 、邊數至多為 的通路。層次為零時,恰在 或存在邊 時返回真。層次為正時,依次枚舉全部 位元標籤 ;若某個 使 與 都為真,就返回真。若全部候選都失敗,則返回假。
對 歸納證明正確性。基礎情況恰好包含零邊及一邊通路。兩條各至多有 條邊的通路拼接後,邊數至多為 。反過來,對於長度 的通路,取經過 條邊後的頂點為中點,兩段長度為 與 ;當 時,兩者均不超過 。空通路可取 。由歸納假設,遞推的兩個方向都成立。
在有 個頂點的圖中,從起點可達的頂點必有一條至多含 條邊的簡單路徑:反覆刪除兩次出現同一頂點之間的部分即可。因此, 為真當且僅當 接受。即使圖中有環,該路徑界限仍成立。
現在計算同時佔用的儲存。一個遞歸堆疊框架保留 、當前中點 、層次 和固定數目的控制標誌。三個標籤佔 位元,層次佔 位元,所以每個框架為 。枚舉計數器僅保存一個 位元串;處理全一串之後設置結束標誌,不需要把全部標籤存下來。層次從 降到零,至多有 個活動框架。
同一中點的兩次遞歸調用按順序執行。第一次返回後先釋放其臨時框架,只保留一個布爾(Boolean)結果,再決定是否執行第二次。因此堆疊空間為 。計算空間界限和邊測試的輔助區域另需 空間,總計 。每次調用只枚舉有限個候選,且子調用層次嚴格下降,所以對層次歸納可知每次調用都停機;計算空間界限的程序亦按假設停機。
證明透視
Savitch 證明各部分各自負責甚麼
這個證明有三個容易混淆的成分。遞推式只是關於通路的陳述:把長度至多為 的通路在中間頂點處分開,兩半的長度都至多為 ,而 的情形處理比界更短的通路。起始層次 來自簡單路徑論證,因為圖有 個標籤;圖中的圈只在這裏才有影響。空間界來自另一處:兩個遞歸調用一先一後地運行,第一個調用的記憶體在第二個開始之前就已釋放,而堆疊至多容納 個各佔 位元的框架。若保留已完成調用的結果,或讓兩個調用並排運行, 的界就會喪失。機器 只透過邊謂詞進入證明,而邊謂詞可在 空間內計算。
遞歸會重複求解相同問題。調用樹的分支數至多為 ,深度至多為 ,故調用總數為 。輸入掃描和標籤比較增加的 的多項式因子可吸收到 中。計算空間界限的確定性停機程序只有 個組態,其時間也被吸收。這是此模擬的時間上界,並非該語言的時間下界。把所有結果都快取下來,會改變空間分析。
概念視角結構
堆疊是調用樹上的一條路徑
把遞歸看成深度為 的子問題樹:詢問 的節點逐一嘗試各個中點 ,每次嘗試有兩個位於層級 的子節點。確定性的運行以深度優先方式走訪節點。任何時刻,只有從根到當前節點的一條路徑上的節點是活動的,所以記憶體是路徑長度 乘以框架大小 ,不論整棵樹有多少節點。
例題詳解
例題 3.2.4
(從對數空間到對數平方空間)
設 在固定字母表上最多使用 個工作儲存格。組態數為 的多項式,標籤寬度為 ,活動遞歸層數也是 。兩者相乘得到確定性空間 ,而非 。因此,單靠 Savitch 定理不能證明 。
例題 3.2.5
(多項式空間仍然是多項式)
若非確定性判定器使用 空間,模擬器使用 空間。次數變了,但仍為多項式。定義 ,並用確定性機器類似定義 。Savitch 定理給出前者包含於後者;把確定性機器看作每步只有一個選擇的非確定性機器,又得到反向包含。因此 。這沒有證明三次空間等於六次空間:類相等依賴於對所有多項式界限取聯集。
例題 3.2.6
(中點不一定把長度平分為相同整數)
設僅有邊 、、。查詢 容許四條邊,但實際見證只有三條。取 ,兩段長度分別為一和二,所以兩個層次一的調用都成功。若錯誤地要求每段恰有兩條邊,則會拒絕,因為這裏不存在四邊通路。「至多」及基礎情況中的 容許較短路徑,不必向圖中加入自環。
按需模擬歸約的輸出帶
上一節的對數空間歸約可能輸出一個多項式大小的圖。把歸約與小空間圖算法複合時,同樣不能先保存全部輸出。
命題 3.2.7
(按需輸出模擬)
設確定性對數空間轉換器 停機,輸出長度有多項式上界,並使用先前內容不影響轉移的唯寫輸出帶。若語言 的判定器在長度為 的輸入上使用 空間,則 可用 空間判定。
證明
(證明)
先運行 ,只計數輸出符號而不儲存它們,以求出 。輸出長度有多項式上界,所以計數器只需 位元。模擬 的判定器,保存其工作帶及虛擬輸入讀頭的位置 。每當它請求位置 的符號,就從頭重跑 ,數到第 個輸出符號並返回它; 以外的端點位置返回相應標記。
重跑轉換器需要 輔助空間,暫停中的判定器保留 空間。二者相加仍滿足界限。每次重跑及被模擬的判定器都停機,而它讀取的恰是 ,故模擬正確。
例如,若輸出是鄰接矩陣,查詢某一項時便重跑歸約,直至它輸出該項。重新計算很長的前綴耗時,卻只需少量可重用記憶體。此命題與之前的 NL 完全性歸約及確定性可達性證明結合,也能推出 ,不必引用一般定理。
常見錯誤與證明界限
常見錯誤
(一般可達性圖中的環)
圖中若有邊 、 及 ,接受通路可以先繞環多次才到達 。後來的選擇可以離開環,所以重複頂點並不迫使每種後續選擇永遠循環。然而,不斷選擇繞環會產生無限通路。因此,該例不能是每條分支都停機的判定器的組態圖的可達部分。刪除環說明即使在一般圖中也存在較短接受見證,卻不限制一般圖中每條通路的長度。我們的搜尋證明也適用於這個更廣的情形。
下界 用於支付輸入讀頭欄位的空間。沒有它,顯示出的編碼大小只是 ,本證明便不能給出 。也不能隨意選擇一個不可計算的空間預算,卻假定模擬器知道如何劃定它;空間可構造性正是提供這一程序。這是在說明本證明的適用範圍,並非斷言所有表述都必須有相同假設。
反例模式
以「每個中點」代替「某個中點」
一個誘人的變體,是把「某個中點可行」改為「每個中點都可行」,期望藉此同時模擬全稱選擇。取頂點 、 和一個孤立頂點 ,僅有一條邊 。此時 應當成立,因為 經一條邊即可到達。取中點 時, 與 都成立, 亦然。但取 時, 不成立,因為 且沒有邊 。於是全稱規則回答為假,儘管 可達。遞推式只有在存在性選擇之下才正確;兼有兩種選擇的交替式機器須另作分析。
練習
快速檢查
(為何可以把從 不可達的組態標籤留在圖中?為何隨意加入從可達組態出發的邊會有危險?)
解答 · 答案
從可達組態出發的每條邊都經過轉移檢查,所以沿路徑歸納始終保持合法可達性;別處的有效組態不會製造假陽性。但任意加入邊可能把可達區域接到原本不可達的組態,再通向接受組態,破壞這一不變量。例如,直接加一條從初始組態到接受組態的邊,就可能把拒絕變為接受。
快速檢查
(一部機器有 個狀態、包括空白符號的二元工作字母表,輸入長度為 ,工作窗口含 個儲存格。計算組態數上界,並給出加上目標後足夠的遞歸層次。)
解答 · 答案
上界為 。加上目標後至多有 個頂點,所以簡單路徑至多有 條邊,層次 已足夠。證明中的顯式編碼使用 位元和層次 ,這是較大但同樣足夠的選擇。
快速檢查
(說明為甚麼保留所有已經完成的子問題的實現可能失去 空間界限。)
解答 · 答案
單一層次可有 對端點,因此為所有端點對保存答案的表可能需要指數多個條目。Savitch 的堆疊只保留 個活動框架,刻意重算已經完成的問題。這是某種快取實現可能付出的代價,不是對所有算法的下界。
快速檢查
(將定理用於 ,寫出確定性空間界限及此模擬的時間上界。)
解答 · 答案
空間為 。由 得到搜尋時間上界 ,其中已吸收輸入掃描因子。
快速檢查
( 是否推出 或 ?明確解釋證明實際上提供了甚麼。)
解答 · 答案
兩個結論都不由本論證推出。多項式的平方仍屬於所有多項式空間界限的聯集;對數的平方則給出一個更大的已陳述界限。該構造也沒有提供非確定性的多項式時間模擬。
快速檢查
(若歸約輸出長度至多為 ,虛擬輸入讀頭需要多少空間?為何重跑歸約會保持該位置的符號不變?)
解答 · 答案
位置至多為 加端點標記,因此需 位元。確定性轉換器在相同固定輸入上從頭運行,總會輸出相同序列;數到保存的位置就得到同一符號,不必保留以前的輸出。
關鍵計算現在已明確:每個組態佔 位元,搜尋有 個活動層次,順序子調用重用臨時空間。非確定性空間的補封閉及多項式空間完全問題等後續主題,還需要新的論證。