一个 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 都成功,则达到该上界。