动机
多项式层级由交替出现的多项式长度量词,后接一个可高效检验的谓词来定义。为了构造具体的完全问题,我们希望该谓词是一个布尔(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 中检验?)
让全称量词对各子句分配。
解答 · 答案
猜出 ,并对每个剩余子句检验它是否为全称重言式。一个剩余子句对全称量化为真,当且仅当它的存在量词部分已经为真,或者它同时含有某个全称文字及其否定。