動機
多項式層級由交替出現的多項式長度量詞,後接一個可高效檢驗的謂詞來定義。為了構造具體的完全問題,我們希望該謂詞是一個布爾(Boolean)公式。多項式時間計算可以用多項式規模的電路表示,但若把一個帶有共用結構的電路盲目展開成公式,規模可能變成指數級。引入閘變量可以保持規模;微妙之處在於:應當在何處對這些變量量化,才不會產生額外的一次交替。
最後一個量詞決定答案。若末塊為存在量詞,我們問是否存在一個一致的、接受的閘賦值。若末塊為全稱量詞,則要求每個一致的閘賦值都是接受的。一致性唯一確定一個賦值,因此兩種檢驗表達的是同一個電路值。
定義
定義 8.2.1
(固定交替次數的量化公式)
固定整數 。一個 量化布爾公式是形如
的良構表達式,其中 是布爾公式,這 個塊是兩兩不相交的布爾變量列表,並且從存在量詞塊開始交替。某個塊可以為空;此時它只有一個賦值,即空串給出的賦值。相應的 問題從全稱量詞塊開始並交替。整數 是問題定義的一部分而被固定,並不是作為無界的輸入參數給出。無效的編碼由確定性算法直接拒絕。
層級類 與 採用類似的定義:固定個數的、交替出現的多項式長度字串塊,後接一個多項式時間謂詞。確定性多項式時間多對一歸約把 映射為一個公式,該公式為真當且僅當 屬於相應的語言。
我們使用配套的「驗證者到電路」單元中的標準一致電路構造:給定固定的多項式時間謂詞 與長度界,可在多項式時間內得到一個多項式規模的布爾電路,它在指定長度的所有輸入上計算 。輸入 可以硬編碼進該電路。
定理
定理 8.2.2
(固定交替次數的公式完全性)
對每個固定的 , 量化布爾公式的真值問題在確定性多項式時間多對一歸約下是 完全的。相應的 公式的真值問題是 完全的。
當 時,存在量詞的問題就是普通的公式可滿足性問題。對更大的固定 ,該定理給出的是該層級上的一個完全問題。它並不能說明兩個層級不同,並且它也不同於帶有無界個數交替塊的公式問題。
概念視角算法
把量化公式看成一場博弈
把每個塊看成一場共 回合博弈中的一步。塊 的擁有者在看到先前各塊之後選取其值:存在方擁有存在量詞塊,全稱方擁有全稱量詞塊。公式為真,恰當存在方有一個策略(每次選擇都可依賴先前的走步),使 對對手的每一種走法都成立。這就是次序重要的原因:在 中, 的選擇可以依賴 。
證明
證明
(屬於該類與困難性:閘變量)
屬於該類可直接由定義得到:按所示順序對各塊的賦值進行量化,並在確定性多項式時間內計算公式的值。任一塊中的變量總數都受輸入長度限制。空塊只有一個可能的空賦值,因此對任一種量詞它都保持真值不變。
對於困難性,取任意 。存在多項式 和確定性多項式時間謂詞 ,使得
其中每個 的長度為 ;不同的多項式界可以透過填充統一,而被忽略的多餘位元不會改變對非空域的量詞。對輸入 ,在多項式時間內構造一個電路 ,它的自由輸入是所有 的位元,其輸出為 。給每個內部閘一個新變量;記這些變量的列表為 。
構造公式 ,它是若干局部約束的合取,這些約束說明每個閘變量都等於該閘的運算作用於其輸入變量或輸入文字的結果。令 表示輸出值;若輸出不是內部閘,則直接使用輸入文字或常數。該公式的規模是多項式的,因為每個扇入有界的閘只貢獻一個常數規模的局部約束。對每個固定的 ,恰好有一個對 的賦值滿足 :按拓撲順序對各閘求值即可。在該賦值下 。
若 ,把 加入最後一個存在量詞塊,並使用母式
若 ,把 加入最後一個全稱量詞塊,並使用
蘊涵是布爾縮寫 ,公式規模只增加一個常數倍。對原來的 變量的每個固定賦值,第一種母式存在滿足的 ,當且僅當 。第二種母式對每個 都為真,當且僅當 :不一致的 使蘊涵為真,而唯一一致的賦值給出電路的輸出。因此,這一替換在每個外層量詞之內都保持真值,並且不增加任何新的量詞塊。它同樣保持多項式規模的輸出,並可在多項式時間內計算。
的證明完全相同:採用相應的外層量詞模式,並按其最後一個塊的類型選擇同樣的一致性構造。這就證明了兩個完全性結論。
證明透視
為何最後一個塊決定連接詞
不明顯的一步是閘變量放在哪裏:它們併入已有的最後一個塊,因此不增加交替。這依賴於電路的兩個事實:對每個固定的 ,滿足 的 賦值恰好有一個,存在性與唯一性都來自按拓撲順序求值,而且在該賦值下 。兩種情形都同時用到這兩個事實。對 ,當 時由存在性得到見證,而唯一性說明沒有其他賦值能證明接受。對 ,存在性說明那個一致的賦值必須接受,唯一性則說明不會有另一個一致的賦值使它失敗。
連接詞必須與量詞相配。不一致的賦值並不描述電路,因此存在塊必須不能利用它們(合取使它們為假),全稱塊則必須不被它們證偽(蘊涵使它們為真)。無環性使論證得以完結:若有反饋環,一致的賦值可能不存在,也可能不唯一。
例題詳解
例題 8.2.3
(兩個量詞的順序)
對一位元變量, 為真:取 即可。但 為假:無論固定 取哪個值, 取相反的值都會使等式不成立。相比之下, 為真,因為內層的存在選擇可以依賴於 。量詞順序改變了各個選擇所容許的依賴關係。
例題 8.2.4
(全稱量詞下的閘驗證)
設某電路輸出 ,並有一個閘變量 。它的一致性公式是 。當 時,每個 都滿足 :不一致的選擇 因前件為假而平凡地滿足蘊涵,一致的選擇 則滿足結論。當 時,一致的選擇 使該蘊涵為假。因此,全稱驗證返回的是電路的值,而不是對所有任意閘賦值取合取。
母式的形式取決於最後一個量詞
定理 8.2.5
(合取範式與析取範式版本)
對每個固定的交替模式,當最後一個塊是存在量詞時要求母式為合取範式(CNF)、當最後一個塊是全稱量詞時要求母式為析取範式(DNF),該真值問題對其層級仍然是完全的。無論初始塊是存在量詞還是全稱量詞,結論都同樣成立。
證明
(閘約束給出 CNF 與 DNF)
使用由扇入有界的 AND、OR 和 NOT 閘構成的電路。每個閘的一致性條件都有一個常數規模的 CNF。例如,若 是作用於 的 AND 閘的輸出,則等價式 可表示為
NOT 閘或 OR 閘有類似的常數規模子句集。因此 可以寫成多項式規模的子句合取 。如果輸出是常數或輸入線而不是閘,則把它的斷言處理為相應的常數或單文字公式。
當最後一個塊是存在量詞時,加入單個輸出子句之後, 已經是 CNF。當最後一個塊是全稱量詞時,
每個 是某一個子句的各文字取反後的合取,而 是一個單文字項。結果是一個多項式規模的 DNF。過程中不對各子句的所有組合作分配律展開。前面的證明已經說明這些公式保持被量化的電路值,因此同樣的歸約也證明了對受限母式的困難性。屬於該類仍然是顯然的。
例題 8.2.6
(轉換一個 AND 閘)
對閘 ,上面的 CNF 有三個子句。取它的否定,再加上所斷言的輸出,得到 DNF
當 時,這個 DNF 對 的兩個取值都為真。若 ,則一致的賦值 使每一項都為假。因此,對 作全稱量化檢驗的是該閘的真實輸出。前三項檢測局部不一致;最後一項斷言在一致賦值上接受。
關於相反範式的提醒
最後一個量詞絕不是無關緊要的細節。考慮形如 的公式,其中 是 CNF。這個受限問題屬於 NP:猜出 ,把它代入每個子句,並分別檢驗每個剩下的子句。一個由全稱文字構成的析取式在每個賦值下都為真,當且僅當它同時含有某個變量及其否定,除非該子句的存在量詞部分已經為真。一個不是重言式的剩餘子句,只要把它的每個全稱文字都設為假就可以被證偽。全稱量詞對子句的合取具有分配性,因此逐個子句的檢驗是充分的。
同一個問題也是 NP 困難的:普通的 CNF 公式可以用作 ,而全稱塊可以含有一個並不出現的啞變量。因此它是 NP 完全的。相比之下,該定理對於母式為 DNF 的「存在-全稱」前束給出的是 完全性。這些事實並不證明 不同於 ;它們只表明某一種範式限制有一個更簡單的、已驗證的上界。
例題 8.2.7
(全稱子句可能在某個賦值上失敗)
考慮 。若 ,則兩個子句對每個 都為真。若 ,則剩下的兩個全稱子句都不是重言式,因此每一個都可以通過選取 來證偽;這個合取當然不可能對所有選擇都成立。該公式為真,恰恰是因為存在方可以選 。相比之下,子句 無論 取何值,對每個 都為真。
常見錯誤
這個構造中最常見的錯誤有兩個。
反例模式
同一個連接詞不能用於兩種塊
很容易以為無論最後一個量詞是甚麼,都可以使用 。對全稱的最後一個塊,這是錯的。取閘 作為輸出,並令 ,電路接受。賦值 是不一致的: 為假。於是 為假,因為 使合取式不成立,儘管電路接受。相反的錯誤同樣會出現:在存在塊中使用 ,且 時,不一致的選擇 使前件為假,因此 為真,儘管電路拒絕。正確的配對是:最後一個塊為存在量詞時用合取,為全稱量詞時用蘊涵。
常見錯誤
(另添一個閘塊)
在最後的全稱塊之後再添加一個存在量詞的閘塊,會產生新的交替,電路便不再處於所給的層級之內。僅僅說「電路求值是高效的」並不能為這一改變提供理由。閘變量必須併入已經在最後的那個塊。
常見錯誤
(全稱末塊之後的 CNF)
所述定理容許任何布爾公式作母式。受限的母式需要各自的歸約,並且必須遵守最後一個量詞的類型。例如,母式 為 CNF 的 如上所示屬於 NP,因此除非 ,它不可能是 完全的。
總結
固定的交替量詞模式有自然的完全公式問題。多項式規模的電路藉閘變量變成多項式規模的公式,而存在量詞下的合取或全稱量詞下的蘊涵,把這些變量放進已有的最後一個塊中。這一完全性結果並不解決多項式層級內部的任何分離問題。
練習
快速檢查
(對一位元的 ,判定 的真值。)
讓 依賴於 。
解答 · 答案
為真:對每個 ,選 即可。
快速檢查
(為甚麼閘賦值一致性公式的規模相對於電路規模是多項式的?)
數一數約束的個數。
解答 · 答案
每個扇入有界的閘貢獻一個常數規模的布爾約束;該合取式中每個閘對應一個這樣的約束,並且只使用多項式個變量名。
快速檢查
(若最後一個塊是全稱量詞,解釋為甚麼不一致的閘賦值不可能證偽 。)
哪一種賦值才可能證偽蘊涵?
解答 · 答案
不一致的賦值使前件為假,因此無論結論如何,蘊涵都為真。唯一一致的賦值是僅有的可能證偽它的賦值。
快速檢查
(對最後一個塊為存在量詞的 公式,構造中有甚麼變化?)
看看哪個量詞在最後。
解答 · 答案
把閘變量加入該最後的存在量詞塊,並像任何最後一個塊為存在量詞的情形一樣使用 。初始的全稱塊不改變這一局部步驟。
快速檢查
(一個問題是 完全的,是否就證明它不屬於 ?)
兩個層級有沒有可能重合?
解答 · 答案
不能。若這兩個層級恰好重合,則完全問題也可能屬於較低的層級。完全性給出的是從該層級出發的歸約,而不是無條件的分離。
快速檢查
(為甚麼在這裏,對 CNF 一致性公式取否定就足以得到多項式規模的 DNF?)
對單一個合取式應用德摩根(De Morgan)律。
解答 · 答案
子句合取的否定是各個子句否定的析取。每個被否定的子句是一個項,因此不需要作指數級的分配展開。
快速檢查
(對「存在-全稱」前束,完全性構造給出的是哪一種母式形式:CNF 還是 DNF?)
看最後一個量詞。
解答 · 答案
DNF,因為最後一個塊是全稱量詞,而構造使用的是 。
快速檢查
(為甚麼母式為 CNF 的 可以在 NP 中檢驗?)
讓全稱量詞對各子句分配。
解答 · 答案
猜出 ,並對每個剩餘子句檢驗它是否為全稱重言式。一個剩餘子句對全稱量化為真,當且僅當它的存在量詞部分已經為真,或者它同時含有某個全稱文字及其否定。