NP 驗證者所問的是:是否存在一個簡短的證書。有些命題則自然地帶有交替的選擇:是否存在一個策略,能夠應付每一個簡短的回應?帶量詞的多項式時間謂詞可以將這類問題形式化,而無須假設每個量詞都能被有效地消去。
動機:從證書到策略
NP 中成員資格的證書是單一的靜態對象。要使懷疑者相信某個布爾(Boolean)公式可滿足,只需交出一個賦值,懷疑者便在多項式時間內檢驗它。懷疑者無須回應任何事情,證明者亦無須預先設想懷疑者的反駁。
許多自然的問題具有不同的形態。考慮以下例子:
給定的電路是否存在一組「設計」輸入的設定,使其對「環境」輸入的每一種設定都適用?
在一個有限博弈中,是否存在一個開局着法,使得對手的每一個回應都能得到應對,令先手最終在多項式輪數內獲勝?
兩個布爾公式是否等價,即沒有任何賦值能區分它們?
最後一個問題我們已經很熟悉。它的否定形式「存在某個賦值能區分它們」是一個 NP 命題,因此公式等價是一個 coNP 命題。本單元研究當我們延續此模式時會發生甚麼:先有一個存在量詞區塊,然後是一個全稱量詞區塊,再是一個存在量詞區塊,如此類推,區塊數目固定,而最後以多項式時間檢驗作結。
本單元圍繞三個主題展開。
類別的語法:量詞區塊中究竟允許甚麼,以及為何區塊數目是常數。
類別的代數:取否定會交換 Σ k P \Sigma_k^\mathrm P Σ k P 與 Π k P \Pi_k^\mathrm P Π k P ,加入虛設區塊則得到嵌套。我們證明由多項式空間給出的上界;配套單元證明一個條件坍縮陳述。
量詞次序的語義:為何 ∃ ∀ \exists\forall ∃∀ 與 ∀ ∃ \forall\exists ∀∃ 不同,以及位於全稱量詞內的存在選擇如何成為策略,即先前各選擇的函數。
量詞類別
設 k ≥ 1 k\ge1 k ≥ 1 。若一個語言的成員資格可以用 k k k 個交替的、多項式長度的二進位串區塊來表達(以存在量詞區塊開始),其後接一個確定性多項式時間謂詞,則該語言屬於 Σ k P \Sigma_k^\mathrm P Σ k P 。若一個語言具有類似的、以全稱量詞區塊開始的表達,則它屬於 Π k P \Pi_k^\mathrm P Π k P 。多項式層級 P H \mathrm{PH} PH 是這些類別對所有固定 k k k 的聯集。特別地,Σ 1 P = N P \Sigma_1^\mathrm P=\mathrm{NP} Σ 1 P = NP ,Π 1 P = c o N P \Pi_1^\mathrm P=\mathrm{coNP} Π 1 P = coNP 。
例如,一個 Σ 2 P \Sigma_2^\mathrm P Σ 2 P 陳述具有以下形式
x ∈ L ⟺ ∃ u ∈ { 0 , 1 } p ( ∣ x ∣ ) ∀ v ∈ { 0 , 1 } p ( ∣ x ∣ ) : R ( x , u , v ) = 1 , x\in L\quad\Longleftrightarrow\quad
\exists u\in\{0,1\}^{p(|x|)}\ \forall v\in\{0,1\}^{p(|x|)}:\ R(x,u,v)=1, x ∈ L ⟺ ∃ u ∈ { 0 , 1 } p ( ∣ x ∣ ) ∀ v ∈ { 0 , 1 } p ( ∣ x ∣ ) : R ( x , u , v ) = 1 ,
其中 R R R 可在多項式時間內計算。這些字串可以表示兩階段博弈中的着法:存在方在知道 x x x 的情況下選擇 u u u ,並且必須對每一個回應 v v v 都成功。固定的多項式長度是無害的:較短的證書可以用謂詞所檢查的方式填充。
確切的假設與約定
上面的定義對長度刻意說得不太嚴謹,因此我們固定一些約定,使後面的證明精確。
每個區塊長度是一個係數為非負整數的多項式 p i p_i p i ,使得 p i ( n ) p_i(n) p i ( n ) 可在關於 n n n 的多項式時間內計算。區塊變量取遍 { 0 , 1 } p i ( ∣ x ∣ ) \{0,1\}^{p_i(|x|)} { 0 , 1 } p i ( ∣ x ∣ ) 中的所有字串。這個集合永不為空,因為即使 p i ( n ) = 0 p_i(n)=0 p i ( n ) = 0 ,它也包含空字串。在加入虛設量詞時,所用到的域的性質僅有這種非空性。謂詞 R ( x , w 1 , … , w k ) R(x,w_1,\dots,w_k) R ( x , w 1 , … , w k ) 由一部確定性機器計算,其運行時間以總輸入長度 ∣ x ∣ + ∑ i ∣ w i ∣ |x|+\sum\limits_i|w_i| ∣ x ∣ + i ∑ ∣ w i ∣ 的某個多項式為界。由於每個 ∣ w i ∣ |w_i| ∣ w i ∣ 本身是關於 ∣ x ∣ |x| ∣ x ∣ 的多項式,因此這個時間單就 ∣ x ∣ |x| ∣ x ∣ 而言亦是多項式。
以下兩種無害的正規化將被隨意使用。
等長區塊。 若各區塊的長度 p 1 , … , p k p_1,\dots,p_k p 1 , … , p k 不同,則將每個長度換成多項式 p = ∑ i p i p=\sum\limits_i p_i p = i ∑ p i 。謂詞會計算原來的區塊長度,並忽略未使用的填充位元。由於填充後的字串經截斷便可決定原來的字串,而每個原來的字串都作為某個截斷出現,因此陳述的真值不變。
相鄰的同類區塊可合併。 形如 ∃ a ∃ c \exists a\,\exists c ∃ a ∃ c 的模式等價於在連接後的字串上的單一區塊 ∃ ( a , c ) \exists(a,c) ∃ ( a , c ) ,∀ ∀ \forall\forall ∀∀ 亦然。因此只有交替的次數才重要,在該處含有若干個連續存在量詞的陳述,與只含單一量詞的陳述屬於同一層級。
最後,諸如 Σ k P \Sigma_k^\mathrm P Σ k P 的表達式永遠指固定的整數 k k k 。類別 P H = ⋃ k ≥ 1 Σ k P \mathrm{PH}=\bigcup\limits_{k\ge1}\Sigma_k^\mathrm P PH = k ≥ 1 ⋃ Σ k P 允許不同的語言使用不同的 k k k ,但單一語言不得有隨 ∣ x ∣ |x| ∣ x ∣ 增長的區塊數目。允許區塊數目增長屬於另一種設定;例如,完全量化布爾公式是 PSPACE 完全的,此結果見於量化布爾公式一節。
補集與嵌套
對每個固定的 k ≥ 1 k\ge1 k ≥ 1 ,Σ k P \Sigma_k^\mathrm P Σ k P 語言的補集恰好就是 Π k P \Pi_k^\mathrm P Π k P 語言。此外,Σ k P \Sigma_k^\mathrm P Σ k P 與 Π k P \Pi_k^\mathrm P Π k P 都各自包含於 Σ k + 1 P \Sigma_{k+1}^\mathrm P Σ k + 1 P 與 Π k + 1 P \Pi_{k+1}^\mathrm P Π k + 1 P 之中。
對帶量詞的陳述取否定,會將每個存在量詞與全稱量詞互換,並將最後的多項式時間謂詞取補集,這就在兩個方向上證明了第一個斷言。要增加區塊數目,當需要相反的起始量詞時,在開頭加入一個被謂詞忽略的虛設帶量詞字串;當需要相同的起始量詞時,則在末端加入。由於每個被量化的域皆非空,虛設區塊不會改變真值。這便給出全部四個包含關係。
帶有虛設存在區塊的確定性多項式時間謂詞給出 P ⊆ N P \mathrm P\subseteq\mathrm{NP} P ⊆ NP ;帶有虛設全稱區塊則給出 P ⊆ c o N P \mathrm P\subseteq\mathrm{coNP} P ⊆ coNP 。因此各層級形成一道階梯,而 P H \mathrm{PH} PH 包含 N P ∪ c o N P \mathrm{NP}\cup\mathrm{coNP} NP ∪ coNP 。
請留意該命題沒有說明甚麼。它沒有說 Σ k P = Π k P \Sigma_k^\mathrm P=\Pi_k^\mathrm P Σ k P = Π k P ,亦沒有說這些包含關係是嚴格的。這兩個問題都是未解決的。
一個例子
設輸入是一個布爾公式 ϕ ( u , v ) \phi(u,v) ϕ ( u , v ) ,其變量被劃分為兩個列表。問是否存在對 u u u 的某個賦值,使 ϕ \phi ϕ 對 v v v 的每個賦值都為真。這屬於 Σ 2 P \Sigma_2^\mathrm P Σ 2 P :猜測第一個賦值,對第二個賦值作全稱量化,並在多項式時間內計算該公式。對於 ϕ ( u , v ) = u ∨ v \phi(u,v)=u\lor v ϕ ( u , v ) = u ∨ v ,選取 u = 1 u=1 u = 1 即成功。對於 ϕ ( u , v ) = u ↔ v \phi(u,v)=u\leftrightarrow v ϕ ( u , v ) = u ↔ v ,u u u 的兩個固定值都不能同時適用於 v v v 的兩個值。
選擇的次序、策略與反例
量詞的次序是實質的區別,而不只是記號上的分別。對任何非空域上的每個謂詞 R R R ,
∃ u ∀ v R ( u , v ) ⟹ ∀ v ∃ u R ( u , v ) . \exists u\,\forall v\ R(u,v)\ \Longrightarrow\ \forall v\,\exists u\ R(u,v). ∃ u ∀ v R ( u , v ) ⟹ ∀ v ∃ u R ( u , v ) .
要看出這一點,設 u 0 u_0 u 0 滿足 ∀ v R ( u 0 , v ) \forall v\,R(u_0,v) ∀ v R ( u 0 , v ) 。對於任意給定的 v v v ,同一個 u 0 u_0 u 0 便見證了 ∃ u R ( u , v ) \exists u\,R(u,v) ∃ u R ( u , v ) 。其逆命題並不成立。
反例模式
交換量詞並不保持等價 若聲稱 ∀ v ∃ u R ( u , v ) \forall v\,\exists u\ R(u,v) ∀ v ∃ u R ( u , v ) 蘊涵 ∃ u ∀ v R ( u , v ) \exists u\,\forall v\ R(u,v) ∃ u ∀ v R ( u , v ) ,這個說法是錯的。在一位元字串上取 R ( u , v ) ⟺ u = v R(u,v)\iff u=v R ( u , v ) ⟺ u = v 。當 v = 0 v=0 v = 0 時見證是 u = 0 u=0 u = 0 ,當 v = 1 v=1 v = 1 時見證是 u = 1 u=1 u = 1 ,所以 ∀ v ∃ u R ( u , v ) \forall v\,\exists u\ R(u,v) ∀ v ∃ u R ( u , v ) 為真。但 ∃ u ∀ v R ( u , v ) \exists u\,\forall v\ R(u,v) ∃ u ∀ v R ( u , v ) 為假:u = 0 u=0 u = 0 在 v = 1 v=1 v = 1 處失敗,u = 1 u=1 u = 1 在 v = 0 v=0 v = 0 處失敗。因此兩種次序一般定義不同的語言。只有上面的單向蘊涵成立;兩個陳述要等價,須能在不看 v v v 的情況下選出見證。
這解釋了「策略」一詞。在 ∀ v ∃ u R \forall v\,\exists u\,R ∀ v ∃ u R 中,見證是一個由 v v v 的值到 u u u 的值的函數 f f f 。在上述反例中,f f f 是恆等函數,而單一的常數值無法取代它。在多項式層級中,策略 f f f 的描述可以大至指數級,因為它的定義域 { 0 , 1 } p ( ∣ x ∣ ) \{0,1\}^{p(|x|)} { 0 , 1 } p ( ∣ x ∣ ) 有指數多個點。這就是為何 ∀ ∃ \forall\exists ∀∃ 陳述並非顯然能由單一簡短證書來驗證,也是為何增加量詞區塊有可能增加表達能力。
另一種捷徑同樣行不通。要對 ∃ u ∀ v R ( u , v ) \exists u\,\forall v\ R(u,v) ∃ u ∀ v R ( u , v ) 取否定,必須對每個量詞以及謂詞都取否定。只否定謂詞並不會得到補集。
在一位元字串上,令 R ( u , v ) R(u,v) R ( u , v ) 表示 u = v u=v u = v 。陳述 ∃ u ∀ v R ( u , v ) \exists u\,\forall v\ R(u,v) ∃ u ∀ v R ( u , v ) 為假,因此它的補集為真。但 ∃ u ∀ v ¬ R ( u , v ) \exists u\,\forall v\ \neg R(u,v) ∃ u ∀ v ¬ R ( u , v ) ,即 ∃ u ∀ v ( u ≠ v ) \exists u\,\forall v\ (u\ne v) ∃ u ∀ v ( u = v ) ,同樣為假:當 u = 0 u=0 u = 0 時,值 v = 0 v=0 v = 0 使其不成立;當 u = 1 u=1 u = 1 時,值 v = 1 v=1 v = 1 使其不成立。因此「量詞不變、謂詞取補」在此給出錯誤的答案。正確的補集是 ∀ u ∃ v ( u ≠ v ) \forall u\,\exists v\ (u\ne v) ∀ u ∃ v ( u = v ) ,取 v = 1 − u v=1-u v = 1 − u 即知其為真。
手動求值一個帶量詞的陳述
下一個例子藉著對存在量詞區塊的每個候選者逐一求值,使量詞次序的語義具體化。
設 u = ( u 1 , u 2 ) u=(u_1,u_2) u = ( u 1 , u 2 ) 為兩位元字串,v v v 為單一位元,並令
ϕ ( u , v ) = ( u 1 ∨ v ) ∧ ( u 2 ∨ ¬ v ) . \phi(u,v)=(u_1\lor v)\land(u_2\lor\lnot v). ϕ ( u , v ) = ( u 1 ∨ v ) ∧ ( u 2 ∨ ¬ v ) . 我們判定 ∃ u ∀ v ϕ ( u , v ) \exists u\ \forall v\ \phi(u,v) ∃ u ∀ v ϕ ( u , v ) 。
對固定的 u u u ,在 v v v 的兩個值處求值。
當 v = 0 v=0 v = 0 :第一個子句是 u 1 ∨ 0 = u 1 u_1\lor0=u_1 u 1 ∨ 0 = u 1 ,第二個是 u 2 ∨ 1 = 1 u_2\lor1=1 u 2 ∨ 1 = 1 。因此 ϕ ( u , 0 ) = u 1 \phi(u,0)=u_1 ϕ ( u , 0 ) = u 1 。
當 v = 1 v=1 v = 1 :第一個子句是 u 1 ∨ 1 = 1 u_1\lor1=1 u 1 ∨ 1 = 1 ,第二個是 u 2 ∨ 0 = u 2 u_2\lor0=u_2 u 2 ∨ 0 = u 2 。因此 ϕ ( u , 1 ) = u 2 \phi(u,1)=u_2 ϕ ( u , 1 ) = u 2 。
所以 ∀ v ϕ ( u , v ) \forall v\,\phi(u,v) ∀ v ϕ ( u , v ) 成立,當且僅當 u 1 = 1 u_1=1 u 1 = 1 且 u 2 = 1 u_2=1 u 2 = 1 。四個候選者的表格如下:
因此該陳述為真,且 u = 11 u=11 u = 11 是唯一的見證。在最壞情況下,這需要對 ϕ \phi ϕ 進行 4 ⋅ 2 = 8 4\cdot2=8 4 ⋅ 2 = 8 次求值。
其補集是 ∀ u ∃ v ¬ ϕ ( u , v ) \forall u\,\exists v\ \neg\phi(u,v) ∀ u ∃ v ¬ ϕ ( u , v ) ,一個 Π 2 P \Pi_2^\mathrm P Π 2 P 陳述,它為假。查看該表格,對於三個不成立的 u u u 中的每一個,都有一個駁倒它的 v v v :對於 u = 00 u=00 u = 00 與 u = 01 u=01 u = 01 取 v = 0 v=0 v = 0 (因為 ϕ ( u , 0 ) = u 1 = 0 \phi(u,0)=u_1=0 ϕ ( u , 0 ) = u 1 = 0 ),對於 u = 10 u=10 u = 10 取 v = 1 v=1 v = 1 (因為 ϕ ( u , 1 ) = u 2 = 0 \phi(u,1)=u_2=0 ϕ ( u , 1 ) = u 2 = 0 )。對於 u = 11 u=11 u = 11 則沒有,這正是補集不成立的原因。此處駁倒用的 v v v 的選擇確實依賴於 u u u ,這與上文關於策略的討論一致。
三個區塊與依賴性的角色
下面的例子使用三個區塊,因此當 a , b , c a,b,c a , b , c 為字串時,它屬於 Σ 3 P \Sigma_3^\mathrm P Σ 3 P 。它亦顯示,將一個量詞移到另一個量詞的另一邊會改變答案。
在一位元變量上定義
R ( a , b , c ) = ( a ∧ ( b ⊕ c ) ) ∨ ( ¬ a ∧ b ∧ c ) . R(a,b,c)=\bigl(a\land(b\oplus c)\bigr)\ \lor\ \bigl(\lnot a\land b\land c\bigr). R ( a , b , c ) = ( a ∧ ( b ⊕ c ) ) ∨ ( ¬ a ∧ b ∧ c ) . 判定 ∃ a ∀ b ∃ c R ( a , b , c ) \exists a\ \forall b\ \exists c\ R(a,b,c) ∃ a ∀ b ∃ c R ( a , b , c ) ,並將它與 ∃ a ∃ c ∀ b R ( a , b , c ) \exists a\ \exists c\ \forall b\ R(a,b,c) ∃ a ∃ c ∀ b R ( a , b , c ) 比較。
情況 a = 1 a=1 a = 1 。 此時 ¬ a = 0 \lnot a=0 ¬ a = 0 ,故 R ( 1 , b , c ) = b ⊕ c R(1,b,c)=b\oplus c R ( 1 , b , c ) = b ⊕ c 。對每個 b b b ,選取 c = 1 − b c=1-b c = 1 − b ,得 b ⊕ c = 1 b\oplus c=1 b ⊕ c = 1 。因此 ∀ b ∃ c R ( 1 , b , c ) \forall b\,\exists c\,R(1,b,c) ∀ b ∃ c R ( 1 , b , c ) 為真,而第一個陳述為真,見證為 a = 1 a=1 a = 1 。
情況 a = 0 a=0 a = 0 。 此時 R ( 0 , b , c ) = b ∧ c R(0,b,c)=b\land c R ( 0 , b , c ) = b ∧ c 。當 b = 0 b=0 b = 0 時,無論 c c c 為何,此值皆為 0 0 0 ,所以 ∀ b ∃ c R ( 0 , b , c ) \forall b\,\exists c\,R(0,b,c) ∀ b ∃ c R ( 0 , b , c ) 為假。因此 a = 0 a=0 a = 0 不是見證。
故 ∃ a ∀ b ∃ c R \exists a\,\forall b\,\exists c\,R ∃ a ∀ b ∃ c R 為真,其致勝策略為 a = 1 a=1 a = 1 連同函數 c ( b ) = 1 − b c(b)=1-b c ( b ) = 1 − b 。
對於第二個陳述,數對 ( a , c ) (a,c) ( a , c ) 是在 b b b 之前選定的。
若 a = 1 a=1 a = 1 ,則 R = b ⊕ c R=b\oplus c R = b ⊕ c 。固定的 c c c 在 b = c b=c b = c 時失敗,因為此時 b ⊕ c = 0 b\oplus c=0 b ⊕ c = 0 。
若 a = 0 a=0 a = 0 ,則 R = b ∧ c R=b\land c R = b ∧ c ,它對每個 c c c 在 b = 0 b=0 b = 0 時失敗。
所以沒有數對 ( a , c ) (a,c) ( a , c ) 適用,第二個陳述為假。由於相鄰的量詞 ∃ a ∃ c \exists a\,\exists c ∃ a ∃ c 合併為一個區塊,第二個陳述是 Σ 2 P \Sigma_2^\mathrm P Σ 2 P 型的模式。這個計算顯示,在兩個存在量詞之間插入一個全稱量詞並非無害:對於同一個謂詞,第一個陳述為真而第二個為假。
在多項式空間內求值
上面的暴力求值提示了一個算法。它使用的記憶體極少,儘管可能需要指數時間。
對每個固定的 k ≥ 1 k\ge1 k ≥ 1 ,Σ k P ∪ Π k P ⊆ P S P A C E \Sigma_k^\mathrm P\cup\Pi_k^\mathrm P\subseteq\mathrm{PSPACE} Σ k P ∪ Π k P ⊆ PSPACE 。因此 P H ⊆ P S P A C E \mathrm{PH}\subseteq\mathrm{PSPACE} PH ⊆ PSPACE 。
設 L ∈ Σ k P L\in\Sigma_k^\mathrm P L ∈ Σ k P ,其等長區塊長度為 p ( n ) p(n) p ( n ) ,謂詞為 R R R ,如上述約定所論證。Π k P \Pi_k^\mathrm P Π k P 的情形是對稱的,亦可由 P S P A C E \mathrm{PSPACE} PSPACE 對補集封閉這一事實得出,因為 Π k P \Pi_k^\mathrm P Π k P 由 Σ k P \Sigma_k^\mathrm P Σ k P 語言的補集組成。
對 1 ≤ i ≤ k + 1 1\le i\le k+1 1 ≤ i ≤ k + 1 定義遞歸過程 E v a l ( i , w 1 , … , w i − 1 ) \mathrm{Eval}(i,w_1,\dots,w_{i-1}) Eval ( i , w 1 , … , w i − 1 ) 。若 i = k + 1 i=k+1 i = k + 1 ,它運行 R ( x , w 1 , … , w k ) R(x,w_1,\dots,w_k) R ( x , w 1 , … , w k ) 並返回結果。否則,若區塊 i i i 是存在的,它按字典序枚舉所有字串 w ∈ { 0 , 1 } p ( ∣ x ∣ ) w\in\{0,1\}^{p(|x|)} w ∈ { 0 , 1 } p ( ∣ x ∣ ) ,對每個 w w w 調用 E v a l ( i + 1 , w 1 , … , w i − 1 , w ) \mathrm{Eval}(i+1,w_1,\dots,w_{i-1},w) Eval ( i + 1 , w 1 , … , w i − 1 , w ) ,一旦某次調用返回 1 1 1 便即時返回 1 1 1 ,若沒有任何調用返回 1 1 1 則返回 0 0 0 。若區塊 i i i 是全稱的,則一旦某次調用返回 0 0 0 便即時返回 0 0 0 ,否則返回 1 1 1 。
對 k + 1 − i k+1-i k + 1 − i 作歸納,調用 E v a l ( i , w 1 , … , w i − 1 ) \mathrm{Eval}(i,w_1,\dots,w_{i-1}) Eval ( i , w 1 , … , w i − 1 ) 返回 1 1 1 ,當且僅當對該前綴而言其餘的帶量詞陳述成立。基礎情形 i = k + 1 i=k+1 i = k + 1 依 R R R 的定義即正確。在歸納步驟中,存在區塊恰在某個延伸成功時返回 1 1 1 ,而全稱區塊恰在所有延伸皆成功時返回 1 1 1 。因此 E v a l ( 1 ) \mathrm{Eval}(1) Eval ( 1 ) 判定 L L L 。
就空間而言,同一時間至多有 k + 1 k+1 k + 1 個遞歸框架處於活動狀態。每個框架儲存一個 p ( ∣ x ∣ ) p(|x|) p ( ∣ x ∣ ) 位元的當前字串(它同時充當枚舉計數器)以及常數量的控制資訊。對 R R R 的葉調用在多項式時間內運行,因此使用多項式空間,而該空間在每次葉調用之後被釋放並重複使用。總空間為 O ( k p ( ∣ x ∣ ) ) O\bigl(k\,p(|x|)\bigr) O ( k p ( ∣ x ∣ ) ) 加上 R R R 所需的一個多項式,由於 k k k 固定,故為多項式。
證明透視
多項式空間從何而來 E v a l \mathrm{Eval} Eval 的遞歸樹深度為 k + 1 k+1 k + 1 ,但葉子最多有 2 k p ( ∣ x ∣ ) 2^{k\,p(|x|)} 2 k p ( ∣ x ∣ ) 個,所以樹本身的大小是指數級。證明從不儲存整棵樹:框架在某個區塊開始枚舉時建立,枚舉完畢即被丟棄,因此任何時刻記憶體中只有一條由根到當前節點的路徑。這就是關鍵一步:兄弟子樹一個接一個地探索,同一批位元被重複使用。正確性是另一回事,只靠歸納法:存在區塊是其各子結果的「或」,全稱區塊是「且」,所以提前返回只影響運行時間,不影響答案。
用到兩個假設。固定的 k k k 只用來計算框架的數目:k + 1 k+1 k + 1 個框架,每個 p ( ∣ x ∣ ) p(|x|) p ( ∣ x ∣ ) 位元。若區塊數目隨 ∣ x ∣ |x| ∣ x ∣ 以多項式速度增長,同一遞歸仍只需多項式個、多項式大小的框架,這正是量化布爾公式同樣屬於 P S P A C E \mathrm{PSPACE} PSPACE 的原因。R R R 的運行時間為多項式,則限定了葉調用所用的空間。至於時間,論證沒有任何說明:調用次數是指數級,證明中亦沒有任何一步給出時間下界。
此過程的運行時間至多為 2 k p ( n ) 2^{k\,p(n)} 2 k p ( n ) 乘以一個多項式,因此該命題並未給出有效的算法。例如,當 k = 2 k=2 k = 2 且區塊長度為 10 10 10 時,R R R 最多可能被求值 2 20 = 1,048,576 2^{20}=1{,}048{,}576 2 20 = 1 , 048 , 576 次,而只儲存 20 20 20 位元的賦值。
練習與解答
快速檢查
(對陳述 ∃ u ∀ v R ( x , u , v ) = 1 \exists u\,\forall v\ R(x,u,v)=1 ∃ u ∀ v R ( x , u , v ) = 1 取否定,並指出所得的量詞模式。)
解答 · 答案 其否定為 ∀ u ∃ v R ( x , u , v ) = 0 \forall u\,\exists v\ R(x,u,v)=0 ∀ u ∃ v R ( x , u , v ) = 0 ,這是先全稱後存在的模式,帶有一個取了補集的多項式時間謂詞。
快速檢查
(對一位元的 u , v u,v u , v ,∀ v ∃ u ( u ⊕ v = 1 ) \forall v\,\exists u\ (u\oplus v=1) ∀ v ∃ u ( u ⊕ v = 1 ) 是否為真?)
解答 · 答案 它為真:在看到 v v v 之後,選取 u = 1 − v u=1-v u = 1 − v 。此選擇可以依賴於 v v v ,因為它出現在全稱量詞之內。
以下是更多練習。請在打開解答之前先自行嘗試每一題。
快速檢查
(設 L ∈ N P L\in\mathrm{NP} L ∈ NP 由 x ∈ L ⟺ ∃ u R ( x , u ) = 1 x\in L\iff\exists u\ R(x,u)=1 x ∈ L ⟺ ∃ u R ( x , u ) = 1 給出。把 L L L 寫成一個 Σ 3 P \Sigma_3^\mathrm P Σ 3 P 陳述以及一個 Π 2 P \Pi_2^\mathrm P Π 2 P 陳述,說明虛設區塊放在哪裏,以及為何真值得以保持。)
解答 · 答案 對於 Σ 3 P \Sigma_3^\mathrm P Σ 3 P ,在存在區塊之後附加兩個虛設區塊:x ∈ L ⟺ ∃ u ∀ d 1 ∃ d 2 R ( x , u ) = 1 x\in L\iff\exists u\ \forall d_1\ \exists d_2\ R(x,u)=1 x ∈ L ⟺ ∃ u ∀ d 1 ∃ d 2 R ( x , u ) = 1 ,其中謂詞忽略 d 1 , d 2 d_1,d_2 d 1 , d 2 。其模式為 ∃ ∀ ∃ \exists\forall\exists ∃∀∃ ,因此它有三個以存在量詞開始的交替區塊。對於 Π 2 P \Pi_2^\mathrm P Π 2 P ,在前面加上一個虛設全稱區塊:x ∈ L ⟺ ∀ d ∃ u R ( x , u ) = 1 x\in L\iff\forall d\ \exists u\ R(x,u)=1 x ∈ L ⟺ ∀ d ∃ u R ( x , u ) = 1 。其模式為 ∀ ∃ \forall\exists ∀∃ ,有兩個區塊。在兩種情況下,每個新增的域 { 0 , 1 } m \{0,1\}^{m} { 0 , 1 } m 皆非空,且謂詞不依賴於它,因此對於任何不提及 d d d 的陳述 Ψ \Psi Ψ ,皆有 ∀ d Ψ ⟺ Ψ ⟺ ∃ d Ψ \forall d\,\Psi\iff\Psi\iff\exists d\,\Psi ∀ d Ψ ⟺ Ψ ⟺ ∃ d Ψ 。
練習 8.1.7
(在一位元變量上,判定 ∀ a ∃ b ∀ c [ ( a ∨ b ) ∧ ( ¬ b ∨ c ) ] \forall a\,\exists b\,\forall c\ \bigl[(a\lor b)\land(\lnot b\lor c)\bigr] ∀ a ∃ b ∀ c [ ( a ∨ b ) ∧ ( ¬ b ∨ c ) ] 的真假,並以前束形式寫出其否定。)
核心
提示 (1) 分別處理 a a a 的兩個值,並問對每個值而言哪個 b b b 有可能適用。
解答 (3) 1 取 a = 1 a=1 a = 1
第一個子句是 1 ∨ b = 1 1\lor b=1 1 ∨ b = 1 ,所以我們需要一個 b b b 使 ∀ c ( ¬ b ∨ c ) \forall c\,(\lnot b\lor c) ∀ c ( ¬ b ∨ c ) 成立。取 b = 0 b=0 b = 0 ,則對每個 c c c 都有 ¬ b ∨ c = 1 ∨ c = 1 \lnot b\lor c=1\lor c=1 ¬ b ∨ c = 1 ∨ c = 1 。因此 a = 1 a=1 a = 1 通過。
2 取 a = 0 a=0 a = 0
關鍵一步
若 b = 0 b=0 b = 0 ,第一個子句為 0 0 0 ,立即失敗。若 b = 1 b=1 b = 1 ,第二個子句是 ¬ 1 ∨ c = c \lnot1\lor c=c ¬1 ∨ c = c ,它在 c = 0 c=0 c = 0 時為 0 0 0 。因此對 a = 0 a=0 a = 0 沒有任何 b b b 適用。
依據: 第一個子句化為 b b b ,迫使 b = 1 b=1 b = 1 。
3 判定該陳述並取否定
該陳述要求每個 a a a 都通過,所以它為假,以 a = 0 a=0 a = 0 為見證。其否定以前束形式寫作
∃ a ∀ b ∃ c ¬ [ ( a ∨ b ) ∧ ( ¬ b ∨ c ) ] , \exists a\,\forall b\,\exists c\ \lnot\bigl[(a\lor b)\land(\lnot b\lor c)\bigr], ∃ a ∀ b ∃ c ¬ [ ( a ∨ b ) ∧ ( ¬ b ∨ c ) ] , 它為真:取 a = 0 a=0 a = 0 ;當 b = 0 b=0 b = 0 時第一個子句已經不成立,當 b = 1 b=1 b = 1 時取 c = 0 c=0 c = 0 。
看下一步 (2/3) 全部展開
練習 8.1.8
(證明對每個 k ≥ 1 k\ge1 k ≥ 1 ,類別 Σ k P \Sigma_k^\mathrm P Σ k P 對交集封閉。)
綜合 證明
提示 (1) 解答 (4) 1 把兩個陳述填充至相同的區塊長度
設 L 1 , L 2 ∈ Σ k P L_1,L_2\in\Sigma_k^\mathrm P L 1 , L 2 ∈ Σ k P 分別由謂詞 R 1 , R 2 R_1,R_2 R 1 , R 2 給出。依等長區塊的約定,兩者可使用同一個區塊長度 p p p 。它們寫作 Q 1 a 1 ⋯ Q k a k R 1 Q_1a_1\cdots Q_ka_k\,R_1 Q 1 a 1 ⋯ Q k a k R 1 與 Q 1 b 1 ⋯ Q k b k R 2 Q_1b_1\cdots Q_kb_k\,R_2 Q 1 b 1 ⋯ Q k b k R 2 ,其中 Q 1 , … , Q k Q_1,\dots,Q_k Q 1 , … , Q k 交替出現,且 Q 1 = ∃ Q_1=\exists Q 1 = ∃ 。
2 定義合併後的陳述
令 R ( x , ( a 1 , b 1 ) , … , ( a k , b k ) ) = R 1 ( x , a 1 , … , a k ) ∧ R 2 ( x , b 1 , … , b k ) R(x,(a_1,b_1),\dots,(a_k,b_k))=R_1(x,a_1,\dots,a_k)\land R_2(x,b_1,\dots,b_k) R ( x , ( a 1 , b 1 ) , … , ( a k , b k )) = R 1 ( x , a 1 , … , a k ) ∧ R 2 ( x , b 1 , … , b k ) ,它可在多項式時間內計算。令第 i i i 個區塊以同一個量詞 Q i Q_i Q i 對數對 ( a i , b i ) (a_i,b_i) ( a i , b i ) 作量化。這是一個有 k k k 個以 ∃ \exists ∃ 開始的交替區塊的陳述。
3 將兩組變量分離
關鍵一步
若 φ \varphi φ 不提及 b b b ,ψ \psi ψ 不提及 a a a ,則對 Q ∈ { ∃ , ∀ } Q\in\{\exists,\forall\} Q ∈ { ∃ , ∀ } 有 Q ( a , b ) [ φ ∧ ψ ] ⟺ ( Q a φ ) ∧ ( Q b ψ ) Q(a,b)\,[\varphi\land\psi]\iff(Qa\,\varphi)\land(Qb\,\psi) Q ( a , b ) [ φ ∧ ψ ] ⟺ ( Q a φ ) ∧ ( Q b ψ ) 。先對最內層的數對 Q k ( a k , b k ) Q_k(a_k,b_k) Q k ( a k , b k ) 應用,再對 Q k − 1 Q_{k-1} Q k − 1 應用,如此向外推進。每一階段中,已分離的部分都不再提及被取出的變量。
依據: 各個域皆非空,且兩個合取項都不提及對方的變量。
4 讀出所得的語言
經過 k k k 個階段,合併後的陳述等價於 ( Q 1 a 1 ⋯ Q k a k R 1 ) ∧ ( Q 1 b 1 ⋯ Q k b k R 2 ) \bigl(Q_1a_1\cdots Q_ka_k\,R_1\bigr)\land\bigl(Q_1b_1\cdots Q_kb_k\,R_2\bigr) ( Q 1 a 1 ⋯ Q k a k R 1 ) ∧ ( Q 1 b 1 ⋯ Q k b k R 2 ) 。其語言為 L 1 ∩ L 2 L_1\cap L_2 L 1 ∩ L 2 ,並且屬於 Σ k P \Sigma_k^\mathrm P Σ k P 。把 ∧ \land ∧ 換成 ∨ \lor ∨ ,以同樣方式便得對聯集封閉。
∎ 看下一步 (2/4) 全部展開
快速檢查
(一個 Σ 2 P \Sigma_2^\mathrm P Σ 2 P 陳述的兩個區塊長度皆為 m = 10 m=10 m = 10 。在最壞情況下,遞歸過程可以對謂詞進行多少次求值,並儲存多少位元的賦值?)
數一數有多少個數對 ( u , v ) (u,v) ( u , v ) 。
解答 · 答案 該過程對每個數對 ( u , v ) (u,v) ( u , v ) 至多對謂詞求值一次,因此至多 2 10 ⋅ 2 10 = 2 20 = 1,048,576 2^{10}\cdot2^{10}=2^{20}=1{,}048{,}576 2 10 ⋅ 2 10 = 2 20 = 1 , 048 , 576 次。它對每個活動區塊儲存一個字串,所以是 10 + 10 = 20 10+10=20 10 + 10 = 20 位元的賦值,另加謂詞本身的工作空間與常數大小的控制資訊。提前終止可以減少這個次數。若除最後一個 u u u 之外的每個候選 u u u 都僅在其最後一個 v v v 處失敗,而最後一個 u u u 對每個 v v v 都成功,則達到該上界。