算法可以在一項計算完成後重用記憶體,但已經花費的時間卻無法收回。空間複雜度度量的正是這種可重用的資源。小空間的機器仍然可以運行很長時間,而這個分別在圖的可達性問題中清晰可見。
為何空間需要獨立的計算方式
在較早的單元中,核心資源是計算步數。時間是累積性的資源:每走一步,都會永久計入該計算的成本。記憶體的表現則不同。曾存放中間值的工作帶儲存格可以被覆寫,因此同一小撮儲存格可以先後服務數以千計的子計算。所以,一個以執行步數計算看似昂貴的程序,若以任一時刻所需的不同儲存量計算,可能只需要很少的空間。
本單元有三個目標。第一,確立一個即使在線性大小以下仍然有意義的空間模型,這需要對輸入作出謹慎的約定。第二,證明判定有向圖中某一頂點能否到達另一頂點這個基本問題,可以由僅使用對數工作空間的非確定性機器解決。第三,把空間與時間以及確定性空間聯繫起來:我們證明非確定性對數空間包含於多項式時間,並陳述可達性可在對數平方空間內以確定性方式判定;該證明見另一配套續篇。這些證明都依賴貫穿本單元的同一個想法,即記憶體很小的機器只能處於數目很少的不同情況,而這個限制可以被精確地計算。
圖的可達性是恰當的測試個案,原因有三。它是一個定義清晰的自然問題。它的明顯算法(例如廣度優先搜尋)使用的標記陣列需要與頂點數成線性關係的空間,因此對數界是真正的改進,而不是記帳上的技巧。而且它的表達力足夠強,正如下文所指出,它能刻劃整個類 。
度量空間
定義 3.1.1
(空間類)
使用一條唯讀的輸入帶和一條獨立的可讀寫工作帶;空間是指所訪問的工作帶儲存格數目。 是由確定性機器判定的語言類,這些機器在長度為 的輸入上使用 工作空間。 是相應的非確定性類:屬於語言的輸入至少有一條接受分支,不屬於語言的輸入則沒有接受分支,而且所有分支都遵守空間界限。 是各個確定性多項式空間類的聯集。
唯讀的約定十分重要:若把整條輸入帶計入費用,便已經需要 個儲存格,使對數界對一般輸入不可能成立。工作帶上的計數器仍然可以用 位元來定位輸入中的位置。在此討論非確定性機器時,要求所有分支都會停機,這在下文的可達性算法中是透過明確限制其步數來達成的。
有必要明確說明這個約定容許甚麼。機器可以在兩個方向上自由移動其輸入讀寫頭,讀取讀寫頭下的符號,並且可以隨意多次重新掃描輸入。它不可以在輸入帶上寫入。因此,要記住關於輸入的任何數據,唯一方法是把數據寫在工作帶上,或者讓輸入讀寫頭停留在可以編碼該數據的位置。儲存一個介乎 與 之間的位置需要 位元,這就是為何對數大小的工作帶剛好足以存放固定數目的輸入指標,或固定數目大小為 的多項式的數。這就是 的運作直觀:對數空間機器是一個配備固定數目指標和計數器的有限控制器。
透過猜測路徑判定可達性
命題 3.1.2
(有向可達性屬於 NL)
給定一個有 個頂點的有向圖及指定頂點 ,在標準的顯式圖編碼下,判定是否存在由 到 的有向路徑屬於 。
證明
(以計數器猜測簡單路徑)
若 可達,則一條簡單路徑至多有 條邊:從任何通路中移除圈即可。把當前頂點和一個計數器各以 位元儲存。從 開始,非確定性地選取一個頂點,掃描唯讀輸入以檢查所選的邊是否存在,並把計數器加一。若到達 則接受;一旦已嘗試 條邊便拒絕。一條接受分支描述一條真實的路徑,而每當存在簡單路徑時,它便提供一個接受的選擇序列。所有分支都會停機,並使用對數工作空間。
這個證明的一些細節值得明確說明。 的情況已被涵蓋,因為機器在走任何邊之前,會先測試當前頂點是否等於 ,所以長度為 的空路徑會被接受。邊的檢查使用顯式編碼(無論是鄰接矩陣還是邊列表),並需要輸入中的一個指標。輸入長度是 的多項式,因此這個指標需要 位元。最後,所猜測的頂點在檢查之前會先寫在工作帶上,這再多花費一個 位元的暫存器。總括而言,機器保存固定數目、大小為對數的暫存器。
完備性與 Savitch 定理
有向可達性在對數空間多一歸約下是 NL 完全的;可達性完全性配套單元給出證明。Savitch 定理在配套的 Savitch 定理單元中得到證明;它指出:對於空間可構造的 ,非確定性空間 包含於確定性空間 。因此 ,而且非確定性多項式空間等於 。這些包含關係並不能確立 ,該問題仍未解決。
完備性將可達性的結果轉移到 NL 中每一個語言;可達性完全性配套單元在對數工作空間內構造該歸約,並給出對數平方空間算法。配套單元證明了一般 Savitch 定理,也證明了將對數空間歸約與可達性算法複合所用的輸出帶模擬。
有界搜尋
例題 3.1.3
(圈不需要無界搜尋)
假設圖中有邊 、 和 。機器可以猜測循環 ,但其計數器會迫使該分支在走了規定數目的邊後拒絕。另一條分支猜測 並接受。非確定性接受只需要一條接受分支,並不要求每個選擇都成功。
常見錯誤
(空間與時間是不同的資源)
對數空間算法並不是以對數步數來定義。它可以重複掃描輸入,重用同樣的少數工作儲存格。反過來說,明確儲存所有已訪問的頂點可能需要線性或更大的空間,儘管這樣做使圖的搜尋變得直接了當。
組態與多項式時間上限
記憶體很小的機器只能處於少數幾種不同的情況,而這可以被計算。以下定義使這個想法精確化。
定義 3.1.4
(組態與組態圖)
固定一部機器 ,其狀態集為 ,工作字母表為 ,以及一個長度為 的輸入 。假設輸入由端點標記界定,因此輸入讀寫頭有 個可能的位置。假設 在 上的每條分支至多使用 個工作儲存格。一個組態是一個元組,由當前狀態、輸入讀寫頭位置、工作讀寫頭位置(從 到 的整數)以及 個工作儲存格的內容組成。組態圖 以這些組態作為頂點;當且僅當 的轉移規則在應用於 中輸入讀寫頭下的輸入符號時,容許 作為 一步之後的後繼組態,便有一條由 到 的邊。
的頂點數至多為 ,因為每個分量都可以獨立選取。若 ( 為常數),則 ,由於 和 都是常數,這是 的多項式。因此組態圖有多項式數目的頂點。這就是對數空間與多項式空間的根本分別:當 時,同一計數給出 ,那是指數級。
定理 3.1.5
(對數空間包含於多項式時間)
設 為一部具唯讀輸入帶的非確定性機器,使得在每個長度 的輸入上,每條分支都會停機,並且對某個常數 ,至多使用 個工作儲存格。則 所判定的語言可由一個運行時間為 的多項式的確定性算法判定。因此 。
證明
(計數組態並搜尋圖)
固定一個長度 的輸入 ,並記 ;特別地,。組態數目 至多為 ,如上文所計算,這以 的多項式為界。一個確定性算法按以下方式進行。第一,列舉所有候選組態。第二,對每個有序對 ,判定 是否為 的合法一步後繼,這需要讀取一個輸入符號並查閱有限的轉移表,因此最壞情況下所需時間為 的多項式。第三,在 中從初始組態出發執行廣度優先搜尋,並且恰好在到達某個接受組態時接受。
就正確性而言,由初始組態到接受組態、且每一步都遵守轉移規則的組態序列,恰好就是 在 上的一條接受分支;反之,每條接受分支都是這樣的一條路徑。總時間至多為 次配對測試(每次均為多項式),加上耗時 的搜尋,因此是 的多項式。包含關係 成立,是因為確定性機器就是每一步只有一個選擇的非確定性機器,而 則由於此論證適用於任何上述類型的機器而成立。
證明透視
空間界在多項式時間論證中的位置
這個證明把問題從計算搬到圖上,而空間界只在一處用到:計算頂點的個數。把組態寫成元組,使個數成為若干獨立選擇的乘積,而對數的 把因子 變成多項式。算法本身只是對多項式大小的圖作普通搜尋;它儲存整個圖及其標記,所以是多項式時間的程序,而不是對數空間的程序。當 時,同一個個數是 ,論證只能給出指數界。正確性方向完全不需要這個界:接受分支恰好對應於從初始組態到某個接受組態的路徑。
請注意,這個證明把任意的 計算歸約為多項式大小的圖上的可達性問題,然後在多項式時間內解決該問題。這正是另一篇可達性完全性續篇所證明的「可達性是 NL 完全的」背後的機制。這個證明儲存了圖和搜尋標記,因此是一個多項式時間的程序,而不是對數空間的構造。輸出長度本身並不是障礙,因為對數空間歸約可以使用一條只寫的輸出帶;對數空間構造會按需要產生並測試候選組態對。
更多例題
例題 3.1.6
(為一部具體機器計算組態數目)
假設一部確定性機器有 個狀態和一個二元工作字母表(把空白計為兩個符號之一,因此 )。在長度 的輸入上,保證它至多使用 個工作儲存格;注意 ,所以 。組態數目的上界為
首先,。接著,。最後,。所以至多約有四千一百萬個組態。這個數目遠大於 ,但仍然是多項式大小的集合。相反,若容許該機器使用 個儲存格,僅因子 便已超過 。若該確定性機器停機,它會在少於 步內停機;若有組態重複出現,由於確定性,它便會永遠循環。
例題 3.1.7
(在五頂點圖上運行猜測並檢查的機器)
設頂點為 ,邊為 、、、、,其中 。每個頂點名稱需要 位元,而邊計數器的範圍為 ,同樣需要 位元。考慮查詢 、。其中一條分支猜測 並透過掃描輸入檢查邊 ,然後猜測 ,再猜測 ;走了三條邊之後,當前頂點等於 ,該分支接受。另一條不同的分支猜測 :走了四條邊(即 條)之後,當前頂點為 ,計數器的界限迫使它拒絕。由於存在接受分支,此輸入被接受。
現在考慮 、。從 可到達的頂點恰好是 ,因為頂點 沒有入邊。每條分支要麼猜測一條非邊而在邊檢查時拒絕,要麼沿著此集合內的合法邊前進,最終耗盡計數器。沒有任何分支到達 ,因此沒有接受分支,輸入被拒絕。在兩個查詢中,機器都儲存一個當前頂點、一個猜測和一個計數器,即 位元,另加輸入指標所需的位元。
練習與解答
快速檢查
(為何可到達的目標總可以由至多 條邊的路徑到達?)
解答 · 答案
從任何到達目標的有限通路中,移除重複出現的頂點兩次出現之間的片段。重複這個步驟便得到沒有重複頂點的通路,因此至多有 條邊。
快速檢查
(為何 ?)
解答 · 答案
確定性對數空間機器就是在每一步只有一個可能下一步動作的非確定性機器,所以它滿足相同的空間與接受要求。
更多練習與解答
快速檢查
(一部確定性機器有 個狀態和一個二元工作字母表,並在長度 的輸入上至多使用 個工作儲存格(注意 )。求其組態數目的上界。)
解答 · 答案
上界為 。我們有 ,然後 ,再 。所以至多有 個組態。
快速檢查
(設 ,邊為 、、、。判定頂點 是否可從頂點 到達,並說明猜測並檢查的機器會做甚麼。)
解答 · 答案
從 可到達的頂點依次為 、、、,得到集合 。邊 指向 ,提供的是離開 的途徑,而不是到達 的途徑,而且沒有任何邊以 為終點。因此 不可到達。機器從 開始的每條分支,要麼在邊檢查時失敗,要麼沿著 內的邊前進,直至計數器達到 並拒絕。沒有分支接受,所以答案為否。
快速檢查
(描述一個判定字串 ()所組成語言的對數空間算法。)
解答 · 答案
首先以有限狀態檢查掃描輸入一次,確認其形式為 ,否則拒絕。在第二次掃描期間,保存一個二進位計數器記錄 的數目,它不會超過 ,因此需要 位元。在第三次掃描時,保存第二個計數器記錄 的數目。恰好在兩個計數器相等時接受。只使用了兩個計數器和固定數目的控制狀態,所以工作空間為 。
快速檢查
(直接證明:一部在每個輸入上都停機、且在長度為 的輸入上至多使用 個工作儲存格的確定性機器,其運行步數是多項式數目。)
解答 · 答案
設 為組態數目,根據計數界限它是多項式。一部停機的確定性機器不會兩次訪問同一個組態:重複的組態會迫使計算永遠循環,因為下一個組態是確定的。所以步數少於 ,這是多項式。
快速檢查
(在包含通路 的圖中,利用移除圈的論證產生一條較短的通路,並說明節省了多少條邊。)
解答 · 答案
頂點 在位置 與位置 (從 起計)出現。刪去兩者之間的部分(頂點 和 以及其中一個 )得到通路 。原通路有 條邊,新通路有 條邊,因此節省了 條邊。新通路中使用的邊 來自原通路,所以它存在於圖中。