前一空間單元定義了對數工作空間並證明有向可達性屬於 NL。本單元透過構造組態圖證明相應的困難性結論,再以確定性的中點搜尋取代非確定性猜測。配套的 Savitch 單元證明一般模擬及下文使用的歸約複合引理。
為何有向可達性是 NL 完全的
定義 3.4.1
(對數空間多對一歸約)
對數空間多對一歸約把輸出寫在唯寫輸出帶上,同時只使用對數大小的工作空間。輸出的長度可以是多項式大小:其儲存格不計入工作空間的上界。這一區別正是下一個構造得以成立的原因。我們將逐條邊地產生圖的描述,而不是把圖或廣度優先搜尋的標記保留在記憶體中。
定理 3.4.2
(有向可達性是 NL 完全的)
在對數空間多對一歸約下,對於有向圖的標準明確編碼,有向可達性對 是完全的。
證明
(NL-困難性的證明)
前一空間單元已透過猜測一條長度至多比頂點數少一的路徑,證明了屬於 的成員資格。關於困難性,設 ,並固定 的一個採用標準單側工作帶模型的非確定性對數空間判定機 。長度小於二的有限多個輸入可分別映到硬編碼的可達或不可達實例。其狀態集與工作帶字母表均為固定常數。選取整數常數 ,使得對於每個長度 的輸入,該機器至多訪問 個工作儲存格。對輸入 ,將一個組態定義為由一個狀態、輸入磁頭位置、工作磁頭位置,以及這 個儲存格的內容所組成。候選組態至多有
個。此上界包含了不可能出現的組合;這不構成問題,因為只有從真正起始組態可到達的組態才會影響答案。離開所保留之工作帶視窗的轉移一律略去:空間界保證從真正起始組態出發的任何分支都不需要這些轉移。
為每個候選組態賦予一個互不相同、長度為 位元的數字標籤。輸出一個以這些候選組態為頂點、並另加一個全新匯點的圖。當且僅當 在固定輸入 上的某一次轉移把 變為 時,存在由 至 的弧。從每個接受組態向該全新匯點添加一條弧。由於匯點相異,略去自環不會改變到達匯點的可達性,因此輸出可以是無自環的簡單有向圖。令源點為初始組態,目標為該全新匯點。 的一個接受計算就是從源點到匯點的一條途徑(walk)。反之,每條從源點到匯點的途徑都沿著合法轉移前進,直至到達某個接受組態,因此它描述了一個接受分支。故 恰好當輸出圖中存在一條從源點到匯點的路徑。
尚需證明資源界,而不能僅僅指出該圖的大小是多項式的。使用兩個 位元的計數器,枚舉候選標籤的所有有序對。把每個標籤解碼為一個狀態、各磁頭位置,以及長度為 的工作帶字;解碼後的兩個組態均可放入 的工作空間。為檢驗一個擬議的轉移,掃描唯讀輸入至輸入磁頭所指定的位置,並把這些組態與固定的轉移表比對。在唯寫輸出帶上印出相應的鄰接矩陣位元,並為下一對重用相同的儲存格。候選組態數目與邊數均為多項式,因此此程序在多項式時間內終止。初始組態與接受組態亦在同一工作空間界內被辨認。因此,該圖及其指定頂點可在對數工作空間內產生,從而證明 可歸約至可達性。
證明透視
組態圖歸約依賴甚麼
所構造的圖包含每一個語法上有效的元組,不論它是否出現在真實計算中,而證明只需要兩個事實。可靠性由對路徑長度的歸納得出:源點是真正的起始組態,每條邊都是合法轉移,所以從源點可達的每個頂點都是確實會出現的組態,圖中其他位置的虛假元組不可能位於從源點出發的路徑上。完備性只用到一次空間界:從真正起點出發的每個分支都留在 個儲存格之內,所以截取視窗時沒有丟掉任何需要的轉移。匯點是全新的,每個接受組態恰好貢獻一條新邊,因此 接受等價於可到達匯點。資源界則是關於產生器的另一個論證,而不是關於圖本身。
正確性與空間分析回答的是不同的問題。僅僅存在一個多項式大小的圖並不足夠:歸約必須能夠以對數工作記憶體枚舉出它。反過來說,唯寫輸出帶並不是歸約日後可以重讀的秘密儲存庫;每當需要資訊時,該構造都會重新計算或重新枚舉。一旦取得 NL-困難性,下文的平方對數可達性算法便蘊涵 ,這是利用配套單元中證明的對數空間歸約複合模擬而得;該單元也證明了更強的一般 Savitch 定理。
確定性對數平方算法
前一單元在猜測路徑時使用了非確定性。我們現在以對數平方的代價消除非確定性。
定義 3.4.3
(有界長度的可達性)
對於頂點 和整數 ,以 表示以下陳述:存在一條由 到 、至多有 條邊的有向通路。
命題 3.4.4
(可達性的確定性空間)
在有 個頂點的圖上,有向可達性可以由使用 工作空間的確定性算法判定。
證明
(證明)
定義 恰好在 或 是一條邊時成立。對於 ,我們斷言 成立當且僅當存在頂點 使得 且 。若這樣的 存在,把兩條通路連接起來便得到一條至多有 條邊的通路。反之,取一條由 到 、有 條邊的通路,並令 為該通路在走了 條邊之後的頂點。前半部分有 條邊,後半部分有 條邊,這是因為 給出 ,而 是整數。當 時有 ,取 。
令 ,因此 。根據上一個命題中的簡單路徑論證, 可從 到達當且僅當 成立。以遞歸方式計算 :當 時直接檢視輸入;當 時,依次遍歷所有頂點 ,先測試 ,再測試 ,並在第一次成功時接受。每個堆疊框架儲存 、、迴圈變量 以及層次 。即三個各為 位元的頂點名稱,加上層次所需的 位元。遞歸深度為 ,已完成的子調用的框架會被丟棄並重用。總工作空間為 ,另加讀取輸入所需的指標。
這就是 Savitch 定理中節省空間的機制。遞歸在處理通路的後半部分時,會重用前半部分所用的記憶體。代價是時間:每一層至多作出 次遞歸調用,因此調用次數至多為 ,這是準多項式而不是多項式。
例題 3.4.5
(四頂點路徑上的中點遞歸)
設頂點為 ,邊為 、、,因此 且 。為計算 ,算法依次嘗試中點 。當 時,調用 成立(取其自身的中點 ),但 不成立:它需要一個中點 ,使得 與 各有一條至多一條邊的通路,而這樣的 並不存在。當 時,我們需要 與 。前者以中點 成立,因為 為真,而 為真是由於 是一條邊。後者以中點 成立,因為 和 都是邊。所以 為真,與唯一的通路 (三條邊,不多於 )相符。對於反向查詢 ,沒有任何中點可行,因為頂點 沒有出邊,所以從 出發唯一的通路是空通路;算法在窮盡全部四個中點後正確地回答否。
常見錯誤
(對數平方空間並不代表快速)
當 很大時,上述遞歸使用的記憶體遠少於標記陣列,但它會多次重複相同的子問題。記憶體很小的程序可能以準多項式時間運行,而多項式時間的搜尋(例如廣度優先搜尋)卻可能使用線性記憶體。兩個界限都不蘊涵對方,這就是為何必須分別追蹤這兩種資源。
反例與界限的緊確性
前述結果中的每項假設都有其原因,以下例子說明缺少它們時會出現甚麼失敗。
反例模式
路徑長度的界 n-1 不能再降低
一個誘人的說法是:至多含 條邊的通路已足以判定可達性。在頂點為 、邊為 的有向路徑圖中,從 到 的唯一通路恰好有 條邊,所以一部在僅僅 條邊之後便拒絕的機器,會錯誤地拒絕這個屬於語言的實例。因此界 是緊確的。
計數器不可省略。在邊為 與 且 不可達的圖上,沒有計數器的機器有一條在 與 之間永遠交替的分支。該分支永不停機,違反了所有分支都會停機的約定。計數器確保這部特定機器在該約定下是一個判定器。
反例模式
對數空間不是對數時間
一個誘人的說法是:使用對數工作空間的機器也在對數時間內運行。考慮由 上只含 的字串所組成的語言。它可以透過一次掃描在常數工作空間內判定。然而,沒有任何確定性機器能在少於 步內於 上判定它。從左端點標記開始,輸入讀寫頭至少需要 步才能到達儲存格 。若機器在少於 步內停機並接受 ,則某個儲存格 從未被讀取。把該儲存格改為 不會改變計算,因此該機器也會接受一個不屬於該語言的字串,這是矛盾。
組態計數並不為更大的空間界限給出多項式時間。一部在二元字母表上使用 個工作儲存格的機器可以有 種不同的內容,因此同一論證只給出指數時間的模擬。這與 和 之間尚未解決的關係一致,並不矛盾。
概念視角算法
同一條路徑的兩種資源度量
可達性程序儲存一個頂點和一個計數器,再反覆掃描輸入以驗證每條猜測的邊。計數器把一個分支限制在簡單路徑的長度以內;空間則衡量搜尋期間重用的儲存單元。因此對工作空間的對數上界,並不意味計算步驟也只有對數個。
將歸約視為算法來閱讀
完全性證明從一部固定的機器 出發,並以其輸入 作為歸約的可變輸入。固定 十分重要:它的狀態集、字母表和轉移表的大小都是常數,儘管編碼後的組態以及所得的圖會隨 增長。NL 中的另一個語言可能需要另一部機器,因而需要另一個歸約;完備性並不保證存在一個同時表示所有機器的圖。
歸約有兩項任務。答案的等價性是關於輸出圖中路徑的數學命題。空間界限則是關於產生其編碼的程序的命題。就鄰接矩陣而言,產生器會遍歷標籤的每一個有序對,並輸出一個位元。它可以重新讀取輸入,並為每一對重新計算一次轉移檢驗。所印出的位元數目,以及印出這些位元所需的時間,都與同一時刻佔用的工作格數目並非同一種資源。相反,若把整個矩陣儲存在工作帶上,便會破壞所宣稱的界限。
例題 3.4.6
(一個微小的組態圖)
考慮一部非確定型機器,其起始組態 有兩個合法的後繼組態:一個拒絕組態 和一個接受組態 。假設兩者均會停機。歸約產生頂點 以及一個新的匯點 ,並附帶邊 、 和 。路徑 見證了接受,即使另一條分支是拒絕的。若移除邊 而不加入其他轉移,則 不可達,所有分支均拒絕。此圖表達的是存在式的接受,而不是各分支之間的多數決。
例題 3.4.7
(中點檢驗中的空行走)
設圖有頂點 ,且僅有一條邊 。在第零層, 為真,因為空行走的長度為零; 亦為真,因為該邊存在。因此在第一層,取 即可證明 。至於 ,兩個候選者均不可行: 要求 ,而 要求同一個為假的命題。允許長度為零的片段,正是讓此遞歸式能夠處理短於其上界的路徑,而無須加入人為的自環。
中點法並不會僅因為每個儲存的標籤很短,就構造出多項式時間的判定程序。它在每一層都遍歷所有候選中點,並反覆重新計算子問題。工作帶的分析追蹤的是單一條活躍的遞歸調用鏈,而時間的分析則計算依次進行的大量調用。這個差別正是遞歸能夠節省記憶體,卻不能由此判定 NL 是否等於 L 的原因。
補充練習與解答
快速檢查
(對於遞歸可達性算法,分別就 與 計算遞歸深度,以及每個框架所儲存的頂點位元數。)
解答 · 答案
當 時,,因此有 個層次,而標記為 的頂點各需要 位元。每個框架三個頂點花費 位元,五個框架的頂點共花費 位元。當 時,,得到 個層次,而標記為 的頂點各需要 位元。每個框架三個頂點花費 位元,六個框架共花費 位元。由 躍升至 ,是因為當 越過 的冪時,深度和框架的寬度都增加了。
快速檢查
(對於上面刪去轉移 後的機器,在其組態圖中加入邊 ,同時保持 為拒絕的停機組態。所得的圖從 出發會給出正確答案嗎?請解釋。)
解答 · 答案
不是。所加入的邊斷言拒絕的停機組態可以在一步內到達接受,但機器並無此轉移。這產生路徑 ,但修改後的機器沒有接受分支。圖中的匯點邊必須恰好只從接受組態出發。
快速檢查
(在頂點為 且僅有邊 的圖中,求 和 。)
解答 · 答案
為真,因為空行走使用零條邊,不超過 。 為假:沒有邊離開 ,所以從 出發的唯一行走只會停留在 。
快速檢查
(某歸約使用對數大小的計數器,印出多項式長度的輸出。為何僅憑輸出長度不會與其工作空間界限相矛盾?)
解答 · 答案
輸出帶是唯寫的,在此歸約模型中不計入工作空間。產生器可以輸出每個符號並重用其計數器;它之後不能把輸出帶當作可讀取的記憶體使用。對數界限所針對的是同一時刻所用的工作格數目,而不是最終印出的符號數目。