動機
計數單元介紹了非一致電路;層級單元介紹了交替量詞。本單元研究小型非一致描述能夠表達甚麼,並證明一個獨立的多項式層級條件坍縮。這些結果本身不證明把電路假設與層級坍縮聯繫起來的 Karp–Lipton 定理;該定理在此未加證明。
關於電路的第二個量化結果
一個自然的問題是,非一致性是否允許每個語言都有小電路。答案是否定的,一個簡短的計數論證說明了原因。我們使用一個明確但粗略的編碼上界,證明關於相異布爾(Boolean)函數的數目與小電路的數目之比較的一個簡潔版本。
命題 8.4.1
(小電路計數與難計算的函數)
固定 及整數 。假設基 上每個至多有 個閘(不計輸入)的電路,其描述方式是:對每個閘,從三種類型中選取其類型,並從 個輸入、兩個常數及較早的閘中選取其輸入來源,候選者至多 個。則此類電路所計算的相異函數 的數目至多為 。特別地,若 ,則某個 位元上的函數沒有至多 個閘的電路。
證明
(證明)
將閘 按拓撲順序排列。每個閘 由其類型(三種選擇)及至多兩個輸入來源指定,每個來源選自 個輸入變量、兩個常數 與 ,以及 個較早的閘,即至多 個候選者所成的集合。對於一元閘 ,第二個來源被直接忽略,故對每個閘都計入兩個來源只會多算。因此每個閘至多有 種描述,而 個閘的序列至多有 種描述。最後指定一個閘為輸出,至多貢獻因子 。每個至多有 個閘的電路(以未使用的閘填補較小的電路)在此集合中都有一個描述,而由這類電路計算的每個函數,都由某個描述所定義的電路計算。所以可計算函數的數目至多等於描述的數目。從 到 的函數恰有 個。若描述的數目嚴格小於 ,則某個函數不被任何此類電路計算。
為說明該條件可以滿足,取 及 。則 ,,且 。故描述的數目至多為 ,其中用到 。同時 。由於 ,在此基下某個 位元上的函數需要超過 個閘。此論證是非構造性的:它證明了困難函數的存在,卻沒有給出任何一個。
同一估計給出一個不屬於 的完整語言,而不只是一個困難的十位元函數。對充分大的 ,取 。電路描述數上界的對數為 ,最終小於 。在每個這樣的長度選取字典序最小、未被這些描述計算的真值表 ;對有限多個較短長度任取函數。這些真值表共同定義一個語言。因為 最終超過 的每一個多項式,所以不存在計算該語言的多項式大小電路族。透過枚舉尋找第一個缺失真值表可能非常昂貴;這論證沒有給出該語言的多項式時間判定機。
概念視角組合
把電路看成簡短描述
依證明,至多有 個閘的電路可用至多 個位元寫下,而 個輸入上的真值表有 個位元。命題說的是同一件事,即鴿籠事實:簡短描述比真值表少,所以必有某個真值表沒有簡短描述。當 、 時,描述數少於 ,而真值表有 個。
建議與多項式大小電路族
電路族容許每個輸入長度對應一個不同的有限對象。建議機器(advice machine)以另一種方式表達同樣的自由度:單一多項式時間算法會接收一個依賴於長度的字串,而該字串未必可由長度計算得出。對於給定長度的所有輸入,該字串都是固定的。它不可依賴於特定的輸入,而且同一個算法必須對每個長度都適用。
定義 8.4.2
(多項式建議)
設 為一個語言。若存在一部確定性多項式時間機器 、一個多項式 ,以及長度至多為 的字串 ,使得對每個長度為 的 皆有
則稱在建議的意義下 。
該機器無須負責產生 。這個記法並不表示建議為每個輸入解決一個不同的問題;同一個 服務所有 個長度為 的字串。
定理 8.4.3
(建議與電路刻劃同一個複雜度類)
一個語言具有供確定性多項式時間機器使用的多項式長度建議,當且僅當它具有多項式大小的布爾電路族,且每個輸入長度對應一個電路。
證明
(證明)
首先假設電路 至多有 個閘,其中 為多項式。把 的一個有限描述放入 。每個閘的記錄指明其類型,以及按拓撲序排列的輸入來源索引。每個索引使用 個位元,因此完整描述的長度為多項式。對於輸入 ,一部固定的確定性機器讀取該描述,並按次序對各閘求值,同時保留其布爾值。這需時多項式,並產生 。建議無須可被有效構造:只要這些描述存在便已足夠。
反之,假設 與 滿足建議的定義,且運行時間至多為 ,其中把建議長度計算在內後 為多項式。一個時間為 的計算只會訪問多項式個帶格。以多項式個位元編碼其整個受限的組態,包括帶符號、讀寫頭標記與狀態。對於固定的機器,下一個組態中每個帶格的內容及其讀寫頭標記,均由一個大小為常數的局部鄰域及有限的轉移表所決定。因此,一個多項式大小的布爾電路可以把某一組態的編碼變換為下一組態的編碼。把 個這樣的電路複本串接起來,並以不變的組態填補已停機的計算。初始編碼由輸入變量及 的固定位元構成;常數把這些建議位元硬接線於電路之中。輸出閘讀取最終的接受位元。該電路的大小為 的多項式,並在所有長度為 的輸入上判定 。對於較小的長度,則分別選取有限個電路。由於我們並未假設存在產生序列 的算法,所得的電路族未必是一致的(uniform)。
此構造證明了兩個非一致定義之間的等價性,但並未證明 :若建議總能被有效計算,它便可以在 內部生成,但這裏容許任意的建議。反過來說,若僅知道每個個別輸入都有一個簡短而有幫助的字串,則該字串等於可以接觸輸入本身,這並不是此定義。
反例模式
多項式建議並不使語言可判定
很容易以為帶有多項式建議的語言必然可判定,因為每個建議字串都是有限對象,而 是普通的算法。這個說法是錯的。固定圖靈(Turing)機的一個枚舉 ,令 。取一位元建議:若 停機則 ,否則 ;並令 恰在 是非空的全 字串且 時接受。則 以線性時間運行,,且 恰當 ,所以 。然而 的判定器會判定任一給定的圖靈機在空輸入上是否停機。每個 都存在,但定義從未要求有算法把它找出來。補救辦法是額外假設 可由 在多項式時間內計算;這樣得到的語言確實屬於 ,見練習。
例題 8.4.4
(為每個長度一次性編碼的電路)
對於長度 ,設 利用每個 XOR 的一個固定常數大小的 AND、OR 與 NOT 實現來計算 。其建議可以是由閘類型與來源索引組成的列表。求值器在全部八個長度為三的輸入上接收的都是同一個列表,改變的只有輸入位元。對於 ,電路描述可以是另一個不同的列表。重要的是每個長度皆存在這樣的列表;這個例子恰好也具有簡單的一致模式。
例題 8.4.5
(建議是共用的,而不是為每個輸入各給一個答案)
設 恰好包含第一個位元為 的二位元字串。在長度為二時,單閘電路 對全部四個字串都給出正確答案。若有一條所謂的建議規則,對輸入 指派單一位元 、對輸入 指派 ,那它其實是在看過輸入之後才選擇建議。即使每個個別答案只有一個位元長,這也不是合法的建議序列 。
例題 8.4.6
(某一長度上的非構造性困難函數)
在 時,前述的電路計數界限顯示,至多有 個閘的電路的描述少於 個,而布爾函數則有 個。因此列表中必然缺少某個真值表。這並沒有指出某個特定的困難函數,而且僅憑這一個長度上的下界,並不能排除某個語言存在多項式大小的電路族:漸近電路複雜度所關注的是所有足夠大的長度,以及一個共同的多項式界限。
本單元的兩個論證回答不同問題。電路計數顯示有些語言沒有多項式大小的電路族;條件坍縮則在一致類別滿足某個相等假設時,涉及層級每一層的所有語言。任何一個結論都不能僅由另一個結論推出。應用坍縮證明時,應在整個歸納中保留其假設:正是該假設提供由全稱量詞區塊到 NP 驗證者的轉換。後續的 Karp–Lipton 定理有不同的假設,需要此處未展開的額外論證。
坍縮
若某一層級滿足 ,則多項式層級坍縮至該層級;這個標準定理在此不加證明地陳述。同樣,當交替量詞區塊的數目不預先固定時,帶量詞布爾公式是 PSPACE 完全的;該結果需要另行證明。這兩個陳述都沒有斷言層級各層級之間存在已知的嚴格分離。
儘管一般的坍縮定理在此未予證明,其第一個情形卻有一個簡短而完整的證明,可以顯示其機制。關鍵的觀察是:從 陳述中移去最外層的量詞區塊,會剩下一個關於數對的 陳述。
命題 8.4.7
(來自第一層級的坍縮)
若 ,則對每個 都有 ,因此 。特別地,若 ,則 。
證明
(證明)
假設 。我們對 作歸納以證明 。 的情形即定義。設 。由層級單元中的補集命題,,而依假設這等於 。
設 ,其最外層區塊為長度 的 ,其後是以全稱區塊開始的 個交替區塊,謂詞為 。定義
採用標準的數對編碼,使 可在多項式時間內還原,且其長度至少為 。被量化的長度以該數對長度的某個多項式為界,因此這可由以全稱量詞開始的 個交替區塊加上一個多項式時間謂詞來描述。於是 。設 為 的驗證者,所用證書長度至多為 。則
其中 ;由於數對編碼的長度是 的多項式,這個界是 的多項式。數對 是多項式長度的證書,並在多項式時間內被檢驗,故 。因此 ,而反向的包含關係是嵌套。這便完成歸納。於是 亦成立,所以每個層級都等於 。
若 ,則因為 對補集封閉,。第一部分的假設成立,因此 。
證明透視
假設用在哪裏
歸納假設 只透過補集起作用:它給出 。假設 則恰好只用一次,用來把 讀作 。這就是不明顯的一步:一個成員資格是全稱陳述的語言,獲得了一個存在式的證書 。一旦有了它,外層的 與新的 便是相鄰的存在量詞,合併為單一區塊,於是 個區塊變成了一個。
有兩個細節使論證嚴謹。數對 的長度是 的多項式,因為 ;否則證書長度界 便無法轉化為 的多項式。而沒有 的話,歸納假設只給出 ,這並不提供成員資格的簡短證書,因此全稱區塊無法移除。
同一個歸納,在全程以 取代 ,就是通往一般陳述的標準途徑,但該途徑需要額外的簿記工作,我們在此不予展開。上面的證明亦顯示了為何目前並無已知結果能無條件地迫使層級坍縮:它恰恰利用假設 將全稱陳述轉化為存在陳述,而對於一般的謂詞,目前並不知道有這樣的轉換可用。
常見錯誤
(坍縮至 NP 並不是坍縮至 P)
該命題假設 ,結論是 。它並沒有得出 :目前並不知道 能推出 。只有更強的假設 才給出 。
練習與解答
快速檢查
(若建議機器對長度為 的輸入使用 ,它可否對該長度的每個輸入以不同的字串取代 ?)
想想建議可以依賴於甚麼。
解答 · 答案
不可以。建議由長度所固定,因此對該長度的每個輸入都是相同的。當然,算法在處理該固定建議時可以檢視輸入。
快速檢查
(若某建議序列本身可由 在確定性多項式時間內計算得出,試證明其語言屬於 。)
讓機器自己生成建議。
解答 · 答案
對於輸入 ,計算 ,由 生成 ,然後在 上模擬建議機器。兩個階段均需時多項式,因此其複合亦為多項式時間。
快速檢查
(存在一個需要超過五十個閘的十位元函數,這是否證明某個明確指名的語言不屬於 ?)
想想計數論證有沒有指出缺少的函數,以及它涉及多少個長度。
解答 · 答案
不是。計數證明並沒有指出缺少的是哪一個真值表;此外,它只涉及單一長度與一個固定的閘數界限。要證明不屬於 ,必須排除整個族在所有多項式大小界限下的可能性。