動機
神諭機可以詢問某個固定集合是否包含一個給定字串,並在一步之內得到回答。神諭是一種數學手段:它讓兩類機器獲得同樣的額外資訊,從而考察某種證明技巧能夠推出複雜度類之間的哪些關係。如果一種技巧在任意神諭下都原封不動地成立,那麼這一類型的單個論證,就不可能確立一個在某個神諭世界中不成立的答案。
我們將構造一個神諭,使得相對於它,確定性多項式時間與非確定性多項式時間不同;並利用一個 PSPACE 完全的神諭得到二者相等的世界。這些構造討論的是相對化的複雜度類,並不能判定一般意義下的 P 對 NP 問題。
定義
定義 4.4.1
(神諭機與相對化的類)
神諭 是一個固定的集合。確定性神諭機可以寫下一個查詢字串,並得到一個回答位元,指示該字串是否屬於 ;非確定性神諭機還可以分支。時間界包括寫下查詢的時間,而一次神諭回答只計一步。因此,運行 步的機器不能寫出長於 的查詢。
用 和 分別表示帶有同一神諭 的確定性和非確定性多項式時間機器所判定的語言。按這些定義,並不要求神諭是可計算的,儘管下面的分離構造可以做到可計算。空神諭在相差一個平凡模擬的意義上還原為一般的機器模型。
我們使用真量化布爾(Boolean)公式 TQBF 的多項式空間完全性,該結論來自配套的空間複雜度一章。具體而言,TQBF 屬於 PSPACE,並且每個 PSPACE 語言都有到它的確定性多項式時間多一歸約。此處不重新證明該完全性定理。
定理
定理 4.4.2
(兩種不同的神諭結果)
存在神諭 和 ,使得
前一個分離與後一個相等是關於兩個不同的固定神諭的陳述,對未相對化的複雜度類並不構成矛盾。
主要工作是構造 ,同時保證後面的階段不會改變前面被模擬的機器所觀察到的回答。然後我們取 為 TQBF。
構造分離神諭
對神諭 ,定義一元語言
它屬於 :在輸入 上,非確定性地猜一個 位元字串並向神諭詢問一次。對不是一元串的輸入則拒絕。見證就是被查詢的字串,寫下它需要 時間。
證明
(對每一台帶時鐘的神諭機作對角化)
有效地枚舉由一個確定性神諭程式和一個整數 構成的數對。對第 個數對,令 為該程式在長度為 的輸入上運行 步後被強制停機的版本,超時視為拒絕。每一台確定性多項式時間神諭機都會以足夠寬鬆的時鐘出現在枚舉中:增大指數即可吸收它固定的多項式次數和常數。每個 在任何神諭和任何輸入上都會停機。
在第 階段構造有限集合 ,起始為 。同時記住此前各階段模擬中所有被查詢字串的長度。選取 ,使它大於此前所有選定的長度和所有此前的查詢長度,並且足夠大,使得
這樣的長度是存在的,因為固定的多項式比 增長得慢。用臨時神諭 在輸入 上模擬 :對已在該有限集合中的字串回答「是」,對其他所有查詢回答「否」。令 為該模擬中被查詢的字串所組成的有限集合。
若 接受,則令 :不加入任何長度為 的字串。若它拒絕,則選取一個不在 中的 位元字串 ,令 。這樣的字串存在,因為該模擬至多作出 次查詢。定義最終的神諭為 。
拒絕情形下的加入不會改變模擬中的回答,因為 並未被查詢。後面的階段只在比此前記錄的每一個查詢長度都更大的長度上加入字串,所以它們也不可能改變本階段所見的任何回答。因此, 在 上使用完成後的神諭所作的計算,與被模擬的計算完全相同。此前加入的字串長度小於 ,之後加入的字串長度大於 。於是,在接受的情形下,沒有任何 位元字串屬於 ,故 ;在拒絕的情形下,,故 。兩種情形下 在該輸入上都判斷錯誤。
每一台確定性多項式時間神諭機都帶著適當的時鐘出現在枚舉中,所以沒有一台能判定 。由於 ,這就證明了 。
這些選擇可以做到有效:取滿足所述界的最小 ,並在需要時取字典序最先的合資格 。每個階段都是有限的,因為被模擬的機器帶有時鐘,而臨時神諭是有限集合。要判定給定字串是否屬於 ,運行各階段直至選定長度達到或超過該字串的長度;嚴格遞增保證這一點必然發生,而之後的階段不可能加入該長度的字串。因此,這一具體構造可以給出一個可計算的神諭,儘管計算它並不屬於多項式時間神諭機模型的一部分。
證明透視
保護查詢,而不只是對角線長度
只把後面的對角線長度選得比此前選定的長度更大是不夠的:較早的機器可能查詢了長得多的字串。該構造記錄每一個查詢長度,並把此後所有的加入長度都選在這些長度的最大值之上。在拒絕的情形下,它還在當前長度上選取一個未被查詢的字串。這兩重保護使被模擬的查詢記錄在最終的神諭中保持不變。
例題詳解
例題 4.4.3
(一個有限階段)
設一台被模擬的機器在 上作出少於十六次查詢並拒絕。在十六個四位元字串中,至少有一個未被查詢。加入這樣一個字串,會使該一元輸入屬於 ,同時保持機器剛才看到的每一個回答不變。這只是一個有限的示意;真實的階段還必須使所選長度大於所有此前受保護的查詢長度,並滿足該階段特定的時鐘不等式。
例題 4.4.4
(為甚麼較長的查詢必須受到保護)
在使用輸入長度四的某一階段,機器可能查詢一個十位元字串。如果後面的階段被允許加入恰好這個十位元字串,那麼較早的模擬就可能從回答「否」變為回答「是」,其記錄的輸出也許不再有效。要求下一次加入的長度大於十,就防止了這種特定的破壞。僅僅保護輸入長度四是做不到的。
例題 4.4.5
(未被查詢的見證的存在性)
如果某個模擬在長度 上至多作出 次不同的查詢,它就不可能檢查全部 個七位元字串。因此可以選出一個不在被查詢集合中的字串。證明所用的是所選長度上可能的見證的個數,而不是假定機器的神諭查詢相互獨立或帶有隨機性。
反例模式
為何長度必須勝過時鐘
聲稱:對角階段在任何輸入長度上都有效,所以不等式 只是技術細節。取 ,以及查詢全部八個三位元字串、並恰在某個回答為是時接受的機器。對 的 種選擇,逐一驗證可知:它接受 當且僅當 ,所以它在這個長度上對每個神諭都正確,也就沒有字串可以加入來擊敗它。這部機器只需約 步,這正是各階段必須選取滿足 的 、讓至少一個字串不被查詢的原因。
使兩個類相等的神諭
定理 4.4.6
(一個 PSPACE 完全的神諭)
令 。則
證明
(透過 TQBF 得到的兩個包含關係)
由於 TQBF 在多項式時間多一歸約下是 PSPACE 完全的,每個 PSPACE 語言都可以被一台多項式時間機器判定:它先計算該歸約,再向 作一次查詢。因此 。
反方向則是用多項式空間模擬一台多項式時間的非確定性 神諭機。沿任何一條分支,它只寫下多項式多個符號,並作多項式多次查詢,每次查詢的長度都是多項式。為回答一次查詢,運行 TQBF 的確定性 PSPACE 算法,並在之後重複使用其工作區。以深度優先方式遍歷非確定性計算樹,只要某條分支接受就接受。由多項式多個多項式大小的組態組成的堆疊,加上一次多項式空間的神諭計算,只使用多項式空間,儘管這一模擬可能耗費指數時間。因此 。
平凡的包含關係 使包含鏈閉合,從而證明了相等。「神諭」一詞在這裏是本質的:多項式時間機器被賦予單位成本的 TQBF 成員資格回答;這個證明並沒有把 TQBF 放進一般的 P 中。
例題 4.4.7
(把一次 PSPACE 計算化為一次神諭提問)
給定一個 PSPACE 語言 ,令 為它到 TQBF 的多項式時間歸約。在輸入 上,神諭機計算 ,詢問其是否為真,並返回該回答。歸約與查詢的構造相對於 是多項式的;神諭的回答則由模型提供。這解釋了較低一側的包含關係,而並未宣稱存在一般意義下 TQBF 的多項式時間算法。
這兩個構造意味著甚麼
在本文的討論中,如果一個證明在把所有機器和複雜度類換成相對於任意固定神諭的版本之後依然有效,就稱它為可相對化的證明。若某個統一的證明對每個神諭 都確立了 ,它就會與分離神諭矛盾。若它對每個神諭 都確立了 ,它就會與使二者相等的神諭矛盾。因此,一個解決未相對化問題的證明不可能具有這兩種普遍可相對化的形式中的任何一種。
這是對一種證明策略的限制,並不是說 P 對 NP 問題獨立於一般的公理,也不是說對角化論證毫無用處。證明可以使用在任意神諭訪問下不會保持的性質。該定理也並不斷言所有神諭都給出同一結果:它的力量來自於展示了兩種不同的選擇。
常見錯誤
常見錯誤
(查詢可以比輸入更長)
確定性多項式時間機器可以查詢比其輸入更長的字串,所以在分離構造中只保護此前的輸入長度是不夠的。不等式 保證了在所選長度上存在未被查詢的字串;它並不說明機器不能查詢更長的字串。
常見錯誤
(神諭陳述針對的是固定的神諭)
賦予非確定性機器的是與確定性機器相同的神諭。神諭下的相等或分離並不會自動轉移到空神諭的情形。
總結
對角化構造在每個階段至多加入一個精心選擇的神諭字串,並保護此前所有的查詢長度,從而把一個一元見證語言放進 。一個 PSPACE 完全的神諭則給出相反的相等關係。兩個世界合在一起說明,為甚麼對所有神諭統一成立的論證無法解決 P 對 NP 問題。
練習
快速檢查
(為甚麼對每個神諭 , 都屬於 ?)
解答 · 答案
在輸入 上,猜一個 位元見證並查詢它。當且僅當神諭回答「是」時接受。
快速檢查
(在拒絕的階段,為甚麼在所選長度上必定存在未被查詢的字串? 為甚麼加入這個未被查詢的字串能保持當前的模擬不變?)
解答 · 答案
該長度的字串有 個,而總查詢次數少於 ,所以至少有一個未被查詢。 新字串不在被查詢的集合中,所以加入之後,確定性模擬中的每一次查詢得到的回答都與原來相同。
快速檢查
(為甚麼後面的加入長度必須大於此前的查詢長度,而不只是大於此前的選定輸入長度?)
解答 · 答案
機器可以查詢比其輸入更長的字串。後面的階段若在這樣的長度上加入字串,就可能改變較早記錄中的某個回答。
快速檢查
(如果被模擬的機器在某一階段接受,在該選定長度上如何選取神諭?)
解答 · 答案
在該選定長度上不加入任何字串。此前和此後的加入具有不同的長度,所以最終的神諭在該長度上沒有任何字串。
快速檢查
(為甚麼 TQBF 的完全性蘊含 ? 為甚麼 ?)
解答 · 答案
計算到 TQBF 的多項式時間歸約,並作一次神諭查詢。模型在一步之內提供回答。 以深度優先方式遍歷多項式時間非確定性計算樹,並用可重複使用的多項式空間算法回答每一次多項式長度的 TQBF 查詢。
快速檢查
(分離神諭是否證明了一般的 ? 兩種神諭結果的存在是否說明 P 對 NP 問題獨立於標準公理?)
解答 · 答案
不。只有當兩個類都配備了所構造的神諭時,它才證明分離。 不。它限制的是相對於每個神諭都依然有效的證明論證;它並不是關於一般問題的形式獨立性定理。
快速檢查
(為甚麼可以枚舉帶時鐘的程式與多項式指數的數對?)
解答 · 答案
每台多項式時間神諭機都有某個多項式時間界。一個足夠大的固定指數給出的時鐘可以超過該界,而每個程式與指數的數對都可以被枚舉。
快速檢查
(在選取之後所有的長度之前,一個階段必須保存甚麼資訊?)
解答 · 答案
它必須記錄當前模擬中用到的所有查詢長度,以及此前受保護的長度,使得未來的加入避開所有此前被查詢的字串。