動機
量化布爾(Boolean)公式描述一個博弈:存在量詞的選擇試圖令公式為真,而全稱量詞的選擇則作出挑戰。評估這個博弈可能需要探索指數多個局面,但深度優先搜尋可以重複使用記憶體。反過來,一條簡潔的量化公式亦可以描述一個指數級龐大的組態圖中的可達性。這兩個方向使「真量化布爾公式」成為多項式空間的一個自然完全問題。
定義 3.3.1
(量化布爾公式與 TQBF)
量化布爾公式由布爾變量、聯結詞,以及取值範圍為 的量詞 構成。封閉公式不含自由變量。設 TQBF 為在標準有限編碼下所有為真的封閉量化布爾公式所組成的語言。我們容許巢狀的量化公式,而不僅限於已化為前束範式的公式。標準的變量重新命名及語法編碼可在多項式時間內完成;以下證明並不依賴於把量詞移過任意否定符號。
評估只需多項式空間
命題 3.3.2
(TQBF 屬於 PSPACE)
TQBF 可由確定性多項式空間機器判定。
證明
(以重用堆疊作遞歸求值)
以遞歸方式評估公式。遇到存在量詞時,先在變量設為零的情況下評估其餘公式,如有需要,再在設為一的情況下評估;只要其中一次評估為真,便傳回真。遇到全稱量詞時,只有在兩次評估皆為真時才傳回真。遇到布爾聯結詞時,先評估其運算元,再合併所得的真值。如有需要,會重新命名變量,使各量詞的作用範圍不含糊。
機器儲存當前的變量賦值、指向輸入公式的指標,以及深度至多為公式長度的遞歸堆疊。每個堆疊框架使用多項式個位元,而已完成的遞歸調用會重用其工作空間。總空間為輸入長度的多項式。遞歸調用的次數可以是指數級,因此這是空間上界,而非多項式時間上界。
例題 3.3.3
(兩輪量詞博弈)
命題 為真:看到 之後,選擇 即可。把次序對調後得到 ,此命題為假,因為一個固定的位元 不可能同時等於零和一。遞歸評估器會檢查全稱變量的兩個取值,並在第二個分支重用同一塊記憶體。此例說明了為何後面的選擇可以依賴於前面的選擇。
以簡潔方式描述指數長度的可達性
設有向圖的頂點以 位元字串編碼,而多項式大小的布爾公式 判定所編碼的兩個頂點之間是否有邊。該圖最多可有 個頂點。定義量化公式 ,使其恰好在存在一條由 至 、邊數至多為 的路徑時為真。其基本情形為
等式情形容許長度為零的路徑,當分割後其中一半比另一半短時,這一點十分有用。
直接的遞推式 會重複前一個公式,可使其書寫長度隨 呈指數增長。我們以一個全稱選擇位元來避免這種重複。設 斷言:當 時 ,當 時 。這是一條大小為 的布爾公式,逐位比較相應的位元。定義
其中 為 位元區塊,而 為單一位元。每個新綁定的變量都會重新命名,以避免捕獲。
定理 3.3.4
(選擇位元遞推式)
對每個 ,公式 恰好在存在一條由 至 、邊數至多為 的有向路徑時為真。其書寫長度為 、 及邊公式大小的多項式。
證明
(選擇位元公式的等價性與大小)
基本情形容許零條邊或一條邊的路徑。對於歸納步驟,假設存在一條長度至多為 的路徑。在把它分割為兩條長度至多為 的路徑的位置選取 ;容許其中一半為空。對於 的每個取值,選取唯一被迫的 ,使之對應於其中一半。歸納假設使遞歸公式為真,故 為真。
反過來,若 為真,則其所選取的 必須對 的兩個取值皆成立。選擇位元迫使遞歸的數對在取零時為 ,取一時為 。歸納假設為每一半給出長度至多為 的路徑。把兩者連接起來,便得到長度至多為 的路徑。
所顯示的公式只含 的一個副本。除標準的變量名稱編碼額外開銷外,每一層包裝只增加 個符號。因此經過 層後,其大小為 及基本邊公式的多項式。交替的選擇位元以量詞的選擇取代了語法上的重複;這並不是聲稱評估該公式只需多項式時間。
證明透視
選擇位元如何令公式保持簡短
樸素的遞推式 含有兩份 ,所以長度每一層都加倍,經過 層後達到基本公式大小的 倍。選擇位元公式只含一份 ,並把全稱位元 所選出的數對 交給它,因此長度每層只增加 。等價性的證明在兩個方向上都用到量詞的排列方式:中點 在 之前確定,所以同一個 必須同時適用於兩半; 是全稱的,所以兩半都是真正需要的。存在量詞 並非真正的選擇,因為對每個 ,選擇位元公式已把它們強制確定。這裏沒有任何東西令求值變快:公式描述的是一個指數長的搜尋,多項式空間的求值器仍須把它逐一走完。
例題 3.3.5
(兩條邊的路徑)
對於具有邊 及 的圖,公式 可以選取中點 。若全稱選擇位元取零,被迫的遞歸查詢為 ;若取一,則為 。兩者皆為真。若只存在 ,且沒有其他通往 的路徑,則第二個選擇位元的取值會暴露缺失的一半,從而否決該中點。
常見錯誤
(全稱選擇位元並不選取中點)
中點 是在全稱位元之前以存在方式選取的,它必須對兩半皆成立。若把量詞次序對調為 ,兩個分支便可以使用互不相關的中點,兩條短路徑未必能夠連接。量詞的位置是可達性證明的一部分。
反例模式
調換中點與選擇位元的量詞
假設把 的排列改為 ,使中點可以依賴選擇位元。取一個邊為 、、、 的圖,即兩條互不相連的路徑,所以從 不能到達 。對 ,調換後的公式需要一個 ,使從 到 有至多兩條邊的通路, 可行。對 ,它需要一個 ,使從 到 有至多兩條邊的通路, 可行。因此調換後的公式 為真,儘管 不可達。若採用正確的次序,單一的 必須同時能在兩條邊內從 到達,並能在兩條邊內到達 ;前一個集合是 ,後一個是 ,沒有這樣的 ,公式為假,這正是應有的結果。
TQBF 的 PSPACE 困難性
定理 3.3.6
(TQBF 為 PSPACE 完全)
PSPACE 中的每個語言都可透過多項式時間多對一歸約化為 TQBF。連同成員資格,TQBF 在此類歸約下為 PSPACE 完全。
證明
(編碼空間受限的計算)
固定語言 的一個確定性多項式空間判定器 。對於長度為 的輸入 ,以對某多項式 而言的 個位元編碼一個完整組態:包括有限狀態、輸入磁頭位置、工作磁頭位置,以及受多項式限制的工作帶內容。如有需要,可加大 ,以保留一個相異的接受匯點。候選位元字串至多有 個。實際的起始組態及匯點都有可由 計算得出的明確編碼。
多項式大小的布爾公式 檢驗 是否為 的合法單步後繼,並由每個接受組態向新增的匯點引一條邊。為了看出大小上界,列舉多項式個可能的磁頭位置,以及有限個狀態和轉移規則。對於每一種情況,比較相關的輸入符號,要求指定的狀態及磁頭更新,要求唯一被改動的工作格子帶有其新符號,並要求所有其他工作格子保持不變。把這些多項式大小的情況取析取,便得到該公式;無效的候選編碼沒有出邊。輸入 被硬編碼於此構造之中。
由於 會停機,它接受 恰好當匯點可由其起點到達。任何可到達的頂點都有一條自起點出發的簡單路徑:刪去重複頂點之間的迴圈即可。由於候選頂點至多有 個,通往匯點的簡單路徑所用的邊數少於 。根據選擇位元定理,封閉量化公式 恰好在此情況下為真。由於 及 皆為多項式,其大小及構造時間為 的多項式。因此 當且僅當所產生的量化公式為真。
此歸約包含語法上可能、但不可到達的組態。這並不會產生虛假的接受路徑:由可到達組態出發的每條邊都是真正的轉移,故對路徑長度作歸納,可使整條路徑保持在真正的計算之內。新增的匯點容許存在多個接受組態,而無須讓公式猜測最終會到達哪一個。
以多項式空間模擬互動證明
定義 3.3.7
(互動證明)
互動證明具有一個多項式時間的隨機化驗證者,以及一個不受限制的證明者。完備性要求:對於是實例,存在某個證明者使驗證者以至少 的概率接受;可靠性則要求:對於否實例,每個證明者令驗證者接受的概率至多為 。對於每個交談記錄,驗證者的時間、隨機位元數、訊息數目及容許的訊息長度都受多項式限制。這包括私有隨機性。
定理 3.3.8
(互動證明屬於 PSPACE)
。
證明
(列舉公開對話記錄)
固定一個輸入。把驗證者的隨機帶填補至固定的多項式長度 ,並把互動填補至固定多項式數目的公開訊息輪,提早終止後以明確的填補補足。證明者看得見驗證者的公開訊息,但看不見其私有隨機帶。我們列舉的是公開交談記錄所構成的樹,而不是向證明者揭露隱藏隨機選擇的樹。
在證明者訊息節點,列舉所有容許的下一則訊息,並取後續計數的最大值。在驗證者訊息節點,對所有可能的下一則公開訊息及終結結果,把後續計數加總。在葉節點,交談記錄已固定所有證明者訊息及所有公開的驗證者訊息。列舉 條私有隨機帶,以這些證明者訊息重播確定性的驗證者,並計算那些恰好產生所記錄的公開交談記錄且接受的隨機帶數目。此計數可容納於 個位元。無效或不一致的交談記錄貢獻為零。
此遞歸計算由每個公開歷史出發所能達到的接受隨機帶數目的最大值。驗證者訊息的各分支把一致的私有隨機帶作劃分,故其計數相加。證明者的下一則訊息是根據公開歷史選取的;在該節點取最大值,代表了每個確定性策略,而不容許其依賴於隱藏的隨機硬幣。隨機化的證明者並不能做得更好,因為其選擇是各確定性後續的平均值。在有限的樹中,於每個公開歷史選取一則使其最大化的訊息,便得到單一的確定性最大化策略。
每個遞歸框架儲存迄今的公開交談記錄、一個訊息列舉計數器,以及一個 位元的累加器或最大值。遞歸深度為多項式,而葉節點處的驗證者模擬使用多項式空間;已完成的分支會重用其記憶體。分支及隨機帶的數目可以是指數級,但同時儲存的量為多項式。在根節點,概念上把接受隨機帶數目的最大值除以 ,並與 比較。完備性使其在是實例上至少為 ,可靠性使其在否實例上至多為 。因此,確定性多項式空間機器可判定該語言。
例題 3.3.9
(先取最大值,後取平均)
假設證明者先傳送一個位元 ,其後驗證者擲一枚公平硬幣得到位元 ,並恰好在 時接受。每個固定訊息成功的概率為 ,故最大值為 。若驗證者改為在訊息之前揭示 ,證明者便可選取 ,最大值變為一。公開交談記錄評估器遵守這個次序:它只在證明者實際看見的訊息之後取最大值,而在葉節點才計算私有隨機帶。若 是保密的,在得知其值之後才分別取最大值,會錯誤地給予證明者隱藏的資訊。
反向包含關係 需要為某個 PSPACE 完全問題(例如 TQBF)給出互動協定。配套的和檢驗(sum-check)單元證明了低次數和協定,但要把量化公式轉化為這樣的互動證明,還需要額外的算術化及次數控制論證,此處並未證明。因此,本單元建立的是 TQBF 的完全性及 IP 的上界,而非完整的等式 。
練習與解答
快速檢查
(為甚麼深度優先的量化公式評估器雖然探索指數多個賦值,仍可只使用多項式空間?)
解答 · 答案
它只儲存當前的賦值及遞歸堆疊,並在完成每個分支後重用該空間。分支的數目影響時間,但不一定影響同時儲存的量。
快速檢查
(在選擇位元遞推式中,為甚麼必須在全稱選擇位元之前選取中點?)
解答 · 答案
同一個中點必須對兩個選擇位元取值皆能分割路徑。若較遲才選取,便可容許互不相關的中點,也就不能保證得到連接起來的路徑。
快速檢查
(若一個圖最多有 個已編碼的頂點,簡單路徑長度的一個充分上界是多少?)
解答 · 答案
可到達的頂點有一條至多 條邊的簡單路徑;容許 條邊則是一個方便的充分上界。
快速檢查
(為甚麼選擇位元遞推式的書寫大小為多項式,而樸素的雙副本遞推式則可能不是?)
解答 · 答案
每層選擇位元包裝只含前一個公式的一個副本,並只增加多項式個符號。樸素的遞推式在每一層都含兩個副本,故其書寫大小可以反覆翻倍。
快速檢查
(在互動樹模擬的證明者節點,為甚麼取最大值便已足夠?)
解答 · 答案
對每則可能的訊息,後續都有明確定義的接受概率。隨機化的選擇是這些值的平均,不可能超過它們的最大值;由於訊息集合有限,必然存在使其最大化的確定性選擇。
快速檢查
( 的證明是否建立了反向包含關係?)
解答 · 答案
沒有。反向的方向需要為某個 PSPACE 完全語言給出獨立的互動協定,其中包括此處並未證明的算術化及次數控制工作。