動機
要證明有向圖中某個頂點可達,非確定性機器可以猜出一條路徑並檢查其中的各條邊,同時只需保存當前頂點和一個步數計數器。相反的斷言似乎更難:一次猜測失敗只說明某一條被提議的路徑失敗了,並不說明所有路徑都失敗。非確定性機器在至少有一個分支接受時就接受;因此僅僅交換接受與拒絕,並不能得到該語言的補。
令人意外的想法是對在有限步數內可達的頂點計數。一旦知道了正確的計數值,機器就能證明自己已經列出了全部這些頂點,儘管每個正面的可達性證書是逐個檢驗的。由此得到 。
定義
定義 3.5.1
(非確定性對數空間機器)
非確定性對數空間機器在長度為 的輸入上使用 的工作空間;其唯讀輸入帶和唯寫輸出帶不計入工作空間。若某個計算分支接受,則該輸入被接受。我們要求機器在所有分支上都停機。
定義 3.5.2
(可達層及其大小)
對有向圖 採用顯式的 鄰接矩陣編碼,頂點編號為 ,並附帶合法的源點與目標點下標。其輸入長度 滿足 ,對數空間機器可以驗證該編碼,並重新掃描矩陣來檢驗某條邊是否存在。給定源點 ,令
我們把空途徑計算在內,故 ,。途徑可以重複頂點;這不造成困難,因為我們計數的是頂點而不是途徑。每個可達頂點都有一條長度至多為 的簡單路徑,所以 就是完整的可達集。假設 且源點與目標點是合法頂點;格式錯誤的圖編碼可以在主程序之前被確定性地拒絕。
定義 3.5.3
(有向可達性問題 STCON)
有向可達性問題 STCON 詢問從 出發能否到達 。它的補問題詢問 是否成立。我們使用標準事實:在確定性對數空間多一歸約下,STCON 是 NL 完全的。配套的可達性筆記建立了組態圖歸約。
定理
定理 3.5.4
(歸納計數與不可達性)
有向可達性問題的補屬於 NL。因此 。更一般地,對每個空間可構造的界 ,類 對補運算封閉;下面的證明明確建立的是對數空間的情形。
最後這個更一般的陳述只是為了說明背景而提及;其一般的組態計數與空間核算在此不予證明。下面我們不借助該推廣來證明對數空間的斷言。
命題 3.5.5
(已認證的計數能讓一次掃描得出甚麼結論)
給定正確的值 ,一次有界的非確定性掃描可以在 空間內判定任一指定頂點是否屬於 :至少有一個分支能存活,且每個存活的分支都返回同一個正確答案。對所有頂點重複該掃描,即可計算出正確的 ,並具有同樣的兩條保證。此斷言要求所提供的計數是正確的。
證明
以經驗證的配額取代儲存的集合
機器並不打算把可達集壓縮成一個位向量來儲存。它儲存的是集合的基數,並反覆重建對整個集合的證書。這是兩種不同的資源: 個頂點的任意子集可能需要 個成員位,而其基數只需要對數多個位。單獨的小計數幾乎不透露任何資訊,但與可靠的正面成員證書結合後就變得很有力。
對每個頂點,選擇「不列出」僅僅是一種遺漏,絕不是非成員的證書。選擇「列出」則帶有出示一條經檢驗的途徑的義務。因此,經檢驗的列表必然是真實可達集的子集。若它的基數等於該集合已知的基數,它就必須是整個集合。這是一個有限集合的蘊涵,並不是假設非確定性機器能驗證任意的否定性陳述。
兩個量詞必須分開。每一個通過所有檢查的存活分支都必須正確;否則哪怕只有一個虛假的接受分支,也會破壞可靠性。而當算法應當繼續時,至少有一個分支必須存活;否則,一個正確的斷言可能僅僅因為要求所有猜測都去做不可能的事而被拒絕。列出所有真正可達的頂點並附上有效的途徑,就提供了第二條性質。這一構造證明了這兩條性質,而不是非正式地宣稱某個猜出的列表是窮盡的。
推進一個可達層
證明
(逐層推進計數)
首先假設正確的整數 已經儲存。我們描述一個有界的非確定性程序來計算 。對每個候選頂點 ,按順序掃描頂點 。在每個 處,猜測「列出」或「不列出」。若列出,則猜測一條從 到 、至多含 條邊的途徑,並僅儲存其當前頂點、長度和下一個猜出的頂點來驗證它。若所聲稱的某條邊不存在,或途徑不終止於 ,則立即拒絕。每列出一個 ,就使計數器加一。
在同一次掃描中,若某個被列出的頂點 等於 或有一條指向 的邊,則設定一個標誌。掃描結束時,除非列出的個數等於已儲存的 ,否則拒絕。若通過,則該標誌就是「 是否成立」的正確答案。事實上,所有被列出的頂點都有經驗證的見證,且屬於 。它們互不相同,因為每個 只被掃描一次。恰有 個成員的 的子集就是整個 。反之,存在一種成功的見證選擇:列出 的每個頂點並附有效途徑,不列出其他任何頂點。於是等價關係
就證明了該標誌的合理性。
統計標誌被設定的候選頂點 的個數;這就是 。每次掃描都可能做出新的非確定性選擇,但每個通過基數檢查的掃描所列出的恰好是 。因此每一個存活的分支計算出的下一個計數都相同且正確。至少存在一個存活的分支,因為每個被列出的可達頂點都存在有效的見證途徑。從 開始,對 重複這一過程。
在整個外層遍歷過程中,舊的計數必須一直可用。應保留一個單獨的累加器來存放下一個計數,並為每個候選頂點 重置局部的「已列出」計數器。只有在每個候選頂點都處理完畢之後,下一個計數才能取代舊計數。若過早重用同一個計數器,後面的候選頂點就會把自己的列表與一個只計算了一部分的量比較,而不是與 比較。這一實現細節是保持歸納不變式的一部分,同時仍然只需要固定個數的小計數器。
正面途徑驗證者可以選擇在長度為零到 之間的任意長度處停止。選擇零的分支檢查其當前頂點是否已經是所要求的終點;另一個分支則猜測下一個頂點,檢查對應的邊,並使長度加一。若到達長度上界時仍未到達正確的終點,則拒絕。成員證書之中並不隱藏任何無界搜尋。特別地,源點總有空途徑作為證書,初始層也不例外。
最後,再對所有 掃描一次,使用長度至多為 的見證以及經驗證的計數 。當且僅當掃描存活且沒有列出 時接受。若 不可達,則正確的列表給出一個接受分支。若 可達,則每個存活的列表都包含它,其餘分支全部拒絕。這就在兩個方向上證明了正確性。
在任一時刻,機器儲存 、當前的 與 、當前途徑的頂點與長度、若干不超過 的計數器、當前計數 以及若干標誌。每一項都需要 位。矩陣輸入可以重新掃描以檢驗某條邊,且不保留任何頂點列表或路徑。循環與見證長度都有界,因此每個分支都會停機。顯式編碼滿足 ,所以這是 空間。簡潔的圖編碼相對於其輸入長度可能有指數多個頂點,需要另行分析;本證明不涵蓋這種情形。
證明透視
基數檢查為何承擔整個論證
層推進能夠成功,靠的是兩點。第一,「恰好列出 個互不相同且經驗證的頂點」這項檢查,把正面證書變成一份窮盡的列表: 的一個含 個元素的子集就是 本身,所以每個存活分支上的標誌都正確,而列出全部 又說明存活分支必然存在。第二,正確性是逐層繼承的:所儲存的 正確這一假設在每一層都會用到,它之所以成立,是因為上一層的所有存活分支都算出了正確的計數,並由 開始。舊計數必須在新計數累加期間保持不變;過早覆寫會把列表與錯誤的數字比較。沒有可信的計數,這項檢查就甚麼也證明不了,配額例子正說明了這一點。
證明
(從不可達性到 coNL)
要從不可達性推廣到整個 coNL,設 ,並設 是到 STCON 的確定性對數空間歸約。則 恰好當 是一個不可達性實例。對數空間機器可以在 的虛擬輸出上模擬不可達性算法,在需要時重新計算被請求的輸出位,而不是儲存整個圖。於是 ,即 。取補即得相反的包含關係。
對於通常的停機的對數空間轉換器,這一模擬只有多項式多個虛擬輸入位置:否則,重複出現的內部組態會永遠重複下去,而輸出帶又不能被讀取以改變後續行為。因此,要獲得某個被請求的輸出位,只需用一個位置計數器重新運行該轉換器。同時保存該計數器與不可達性機器的各條工作帶,相對於原輸入長度仍然只用對數空間。這就是為甚麼對數空間歸約下的封閉性不需要把它們的整個輸出實體化出來。
例題詳解
例題 3.5.6
(分層統計可達頂點)
取頂點 與邊 ,,,源點為 。則 ,,。計數依次為 。對於階段 的候選頂點 ,一次掃描必須列出 的三個成員並附上見證。邊 使標誌被設定。只列出 和 的掃描不可能錯誤地把 判為不屬於:它通不過計數檢查。
例題 3.5.7
(含圈的不可達目標)
設圖的邊為 和 ,另有孤立頂點 ,源點為 ,目標點為 。前兩個可達集是 和 ;此後的可達集都保持為 。儘管繞圈的途徑有無窮多條,但每個可達頂點的最短見證至多含一條邊。一次有效的最後掃描列出 而不列出 ,因此某個分支會接受不可達性。
例題 3.5.8
(未經檢驗的較小配額可能隱藏可達頂點)
取五個頂點,源點為一,邊為 ,,。在第一層,真實的可達集是 ,其計數為三。在檢驗四是否屬於下一層時,只列出一和二的掃描具有有效的正面證書,卻遺漏了前驅三。在正確的配額下,它因只列出了兩個而非三個頂點而被拒絕。若允許機器沒有理由地猜測較小的配額二,同一次掃描就會存活,並錯誤地報告四不屬於。逐層的構造透過讓每個配額都源自其經認證的前一個配額,排除了這種情形。
常見錯誤
常見錯誤
(猜測的計數不是經認證的計數)
猜測出來的計數本身不可信。該程序從已知值 出發,並利用前一個正確的值來驗證下一個計數。同樣,也不能簡單地猜測某個未被列出的頂點不可達:基數檢查迫使每個存活的掃描都包含所有可達頂點。
常見錯誤
( 並不給出 )
並不蘊涵 ;它給出的是補問題的非確定性算法,而不是確定性算法。
反例模式
重複計數同一頂點會使配額失效
設掃描可以把同一個頂點列出多次,而只把經驗證的聲稱的個數與 比較。取五個頂點,源點為 ,邊為 ,,,則 ,。一次掃描把頂點 列出兩次、頂點 列出一次,共作出三個經驗證的聲稱,各有有效的途徑( 用空途徑, 用邊 ),因此通過計數檢查。它從未列出 ,所以沒有被列出的頂點有邊指向 , 的標誌保持未設定。於是該掃描報告 ,但 是一條長度為二的途徑。按遞增次序、每個頂點至多列出一次,則經驗證的聲稱構成一個集合,而 的含 個元素的子集必然是整個 。
總結
正面的路徑證書加上一個已經認證的計數,就能迫使得到一個窮盡的列表,而無需儲存它。對相繼的路徑長度上界重複這一觀察,就證明了有向不可達性屬於 NL。這一結果是關於非確定性對數空間算法的存在性陳述;它並沒有給出有向可達性的確定性對數空間算法。
練習
快速檢查
(對於邊 ,,, 以及孤立頂點 ,以 為源點,求 ,並判定目標點 是否可達。)
逐層建立 。
解答 · 答案
可達集依次為 ,,, 和 ,計數為 。頂點 不可達。
快速檢查
(為甚麼驗證掃描只需對每個頂點處理一次?如果同一個頂點被重複計數,會出甚麼問題?)
比較聲稱的個數與互不相同的頂點個數。
解答 · 答案
每個 只處理一次,使得經驗證的聲稱的個數就是一個集合的大小。若允許重複計數,則同一個可達頂點可能被多次列出,從而湊滿配額,而另一個可達頂點卻被遺漏。
快速檢查
(某位同學聲稱,在對 個頂點完成一次掃描後,沒有找到通向 的路徑就證明了不可達。指出缺失的條件。)
某個分支可能根本沒有列出某個頂點。
解答 · 答案
某個分支可以選擇不列出一個可達頂點,或者猜出錯誤的見證。掃描必須驗證每一個正面聲稱,並驗證被列出的互不相同的頂點個數等於已認證的正確可達計數;否則遺漏 甚麼也證明不了。
快速檢查
(在只有一個頂點、且源點與目標點都等於該頂點的圖中,不可達性應當接受嗎?請解釋零長度的情形。)
空途徑算不算途徑?
解答 · 答案
不應接受。空途徑表明源點可達自身,所以 包含目標點。由於 ,最後的列表是 ,每個有效分支都會拒絕不可達性。
快速檢查
(若 ,且 在確定性對數空間多一歸約下也是 NL 難的,證明 在同類歸約下是 coNL 難的。)
從任意的 出發,取其補語言。
解答 · 答案
設 ,即 。由 NL 困難性,存在確定性對數空間函數 ,使得 當且僅當 。取補得 當且僅當 。因此每個 coNL 語言都可歸約到 。