动机
多项式规模的电路族可以对每个输入长度各含一个独立的电路,而不要求存在高效的方法来生成该电路族。即便如此,若假设每个 NP 语言都有小电路算法,也会产生很强的后果。特别地,这将使得一个多项式规模的电路能够为某一固定长度的所有相关输入找到见证。在全称挑战之前先猜测这样一个电路,就把一个“全称—存在”两块量词的陈述转化为“存在—全称”的陈述。
我们在标准的非一致形式下证明 Karp–Lipton 蕴含关系:若 ,则多项式层级等于其第二个存在层 。该假设目前并不知道是否成立,结论也是有条件的。证明并不声称 ,因为非一致电路族未必能由其输入长度计算出来。
我们采用多项式层级的量词定义:特别地, 中的语言具有一个多项式时间谓词 以及多项式有界的定长字符串,使得
通常的填充约定使得每一量词块中的所有字符串都具有指定的长度。我们还把确定型多项式时间计算可由多项式规模电路模拟这一标准结果作为背景知识使用。见证搜索的构造与坍缩论证将在下文中证明。
判定电路可以引导见证搜索
定义 8.3.1
(见证前缀语言)
设 是一个多项式时间谓词,其见证 具有固定的多项式长度 。 的前缀语言为
的验证者猜测 的其余比特,检查 是其前缀,并计算 。因此 。在 的假设下,它具有多项式规模的判定电路,尽管这些电路未必可以一致地构造出来。
定理 8.3.2
(非一致见证搜索)
假设 。对于每个具有固定多项式见证长度界的多项式时间谓词 ,存在一个多项式规模的电路族 ,使得只要长度为 的输入 具有有效见证, 就输出一个有效见证。当不存在见证时,输出可以是任意的。
证明
(证明)
对于输入长度 ,从空前缀开始。在 个位置中的每一个位置上,询问对同一个输入 ,当前前缀后接 0 是否属于 。若是,则追加 0;否则追加 1。若当前前缀存在有效见证,则两个扩展中必有一个具有有效见证,因此这一选择保持该不变式。经过 次选择之后,该前缀就是一个完整的有效见证。对于没有见证的输入,无需做任何正确性断言。
每个查询 的长度以 的某个多项式为界。在固定编码下,这 个阶段所涉及的查询长度由 及所处阶段决定。选取 的相应多项式规模非一致电路,并按需复制。将编码硬连线,并把每个判定电路的输出接入下一阶段的前缀。展开这多项式个阶段,便得到一个多项式规模的电路:多项式个多项式规模的电路副本与多项式时间的编码电路,其总规模是多项式的。它把每个长度为 的输入 映射为一个长度为 的字符串。我们并不假设存在由 生成该电路族的算法。
例题 8.3.3
(沿着可满足赋值的前缀前进)
对于公式 ,空前缀有扩展。询问前缀 是否有扩展:有,即 。于是把第一个比特固定为 0。接着询问 是否是通向可满足赋值的扩展:不是,因此把第二个比特设为 1。搜索返回 。这两次判定依赖于同一个公式,而第二次查询依赖于第一次的回答。展开过程用电路的连线记录这种依赖关系;在所构造的搜索电路中并不枚举全部赋值。
概念视角组合
把搜索看成二叉树上的下降
把所有长度至多为 的前缀排成一棵完全二叉树。当 ,即 之下存在见证时,标记前缀 。搜索从根出发(根被标记当且仅当存在见证),在每个结点处,若以零结尾的子结点被标记就走向它,否则走向以一结尾的子结点。因此它沿着一条被标记的路径走到叶子,每一步需要向 做一次成员查询。
常见错误
(电路族不是一致的搜索算法)
该证明是从一个非一致电路族中为每个相关长度选取判定电路的。它并没有提供一台多项式时间的机器,使其在给定长度后写出这些电路。对于没有见证的输入,搜索电路可以输出任意字符串;之后的验证者仍须检查所提出的见证。这些限定条件对于假设本身以及下文的可靠性论证都是至关重要的。
反例模式
多项式大小电路并不给出判定算法
断言:有多项式大小电路的语言必可判定,所以 不大于 。取 。对每个 ,电路先检查 个输入位是否全为 ,再输出一个固定常数,即第 台机器真实的停机答案。它的大小为 ,所以 。若 可判定,停机问题也就可判定。因此 含有不可判定的语言。修正办法是要求一致性,即存在多项式时间算法能由 产生电路,而本定理并不假设这一点。
为什么 SAT 电路假设已经足够
该假设通常仅用 SAT 来表述。这一等价形式依赖于 SAT 的通常 NP 完全性,以及用多项式规模电路模拟多项式时间归约;我们将这些标准结果作为背景知识使用,并说明如何处理输出长度。
命题 8.3.4
(SAT 电路足以给出 NP 电路)
若 SAT 具有多项式规模的非一致电路,则 。反之,后一包含关系蕴含 SAT 具有多项式规模的电路。
证明
(证明)
对于 ,选取从 到 SAT 的多项式时间多一归约 。在长度为 的输入上,它产生的编码长度至多为某个多项式 。一个多项式规模的电路模拟 ,同时输出填充后的编码及其实际长度 。对于每个可能的 ,选取针对长度 的输入的 SAT 电路。把输出的前 个比特送入该电路,并利用所计算出的长度来选择其回答。格式错误的编码按照固定的 SAT 编码被拒绝。可能的 只有多项式个,且每个被选取的电路规模都是多项式的,因此组合而成的电路关于 的规模是多项式的,并且判定 。该电路族的选取是非一致的。逆命题是显然的,因为 SAT 属于 NP。
例题 8.3.5
(为什么不能默默忽略输出长度)
一个归约可能对某个长度为 的输入输出较短的公式,而对另一个同样长度为 的输入输出较长的公式。电路族对每个实际长度各有一个不同的电路,因此仅仅选取最大长度对应的电路,并向其输入任意填充的编码是不够的。选择器构造对每个可能的长度计算相应的正确电路;它并不假设填充会保持所选编码的含义。
同样的有限长度记账方式也出现在见证搜索定理中。若每个前缀查询的长度至多为 ,且判定电路的规模至多为 ,则 个阶段至多使用 个判定门,再加上多项式规模的编码与连线开销。 与 均为多项式,因此所得的界是多项式的。该电路允许包含许多副本,但并不包含记录所有可能见证的指数规模的表。
将“全称—存在”陈述移至第二个存在层
定理 8.3.6
(Karp–Lipton 关键包含关系)
若 ,则 。
证明
(证明)
设 由上面所示的谓词 给出,并固定输入长度 。利用多项式时间可解码的定长编码构成 。见证长度 是 的多项式,并且可以从该编码中恢复。若有需要,先填充长度,再将见证搜索定理应用于关系 。它给出一个多项式规模的电路:对于规定长度的每一对 ,只要存在某个有效的 ,该电路就输出一个有效的 。
对于固定的输入 ,把 硬连线到该电路中。所得的多项式规模电路 以 为输入,输出一个候选 。其描述长度以 的多项式为界,且对所有长度为 的输入使用同一个多项式界。考虑如下陈述:
检查 的格式是否良好、计算 、检查输出长度以及计算 ,所需时间都是关于 与描述长度的多项式。将描述填充为固定的多项式长度,并拒绝无效的编码。因此该陈述属于 。
若 ,则每个 都有见证,硬连线的见证搜索电路对所有 同时有效;存在性的电路描述存在。若 ,则某个 没有有效见证。对该 ,任何电路的输出都无法满足 ,因此任何被猜测的电路都不可能使全称检查通过。于是该陈述恰好定义了 。
证明透视
为什么猜测电路会交换量词
命题 所要求的见证 ,可以任意地、甚至以指数级复杂的方式依赖于 。证明把这种依赖转化为短到足以被猜测的东西:一个由 算出 的多项式规模电路 。这是唯一不寻常的一步,也正是 的用处所在:根据非一致见证搜索定理,只要依赖关系 真的存在,它总能由一个小电路实现。此后,对 的存在选择便排在全称的 之前,得到 。
有两点使证明严谨。电路是在 固定之后才选的,因此可以把 硬连线进去, 只需对这个 适用。并且检验 是对每个 进行的,所以错误的猜测绝不可能通过:若某个 没有有效的 ,则无论 是什么, 都不满足 。这就是电路在没有见证的输入上可以输出任意内容,而不损害可靠性的原因。没有该假设,就没有理由认为存在这样简短的描述,被猜测的对象也就无法以多项式为界。
例题 8.3.7
(被猜测的电路必须完成什么)
设一个玩具谓词要求:对每个两比特的 ,存在一个等于 按位取补的两比特 。电路 对全部四个 值都成功,因此一个描述即可通过全称检查。若修改该谓词,使 没有有效的回应,则无论设计者的能力多强,每个被提出的电路在该 处都会失败。这个有限的例子说明量词转换的完备性与可靠性;它并没有确立 NP 的小电路假设。
被存在性猜测的对象是一个电路,它必须对给定 的每一个 都能处理。它并不是在每次全称挑战之后才另行选出的存在性见证。反过来,该电路不必对与此 无关的数对正确;硬连线 是允许的,因为外层的存在性选择是在输入已知之后作出的。
其余各层的坍缩
取补运算互换 与 。对关键包含关系取补,得到 ,因此两个第二层相等。下面给出归纳论证,以推出每个更高的层都等于它们。
定理 8.3.8
(Karp–Lipton 坍缩)
若 ,则 。
证明
(证明)
基础等式如上所述。假设对某个 有 。一个 陈述由一个外层存在量词块后接一个 谓词构成。由归纳假设,该内层谓词具有一个以存在量词块开头的 描述。把相邻的两个存在量词块合并为一个多项式长度的块。这就给出了一个 描述,因此 。反向包含关系通过添加哑量词块得到。
取补得到 。归纳法证明了第二层及以上的所有层都等于第二层。第一层由嵌套关系包含于其中,因此所有固定层之并,即 PH,等于 。
例题 8.3.9
(合并相邻的存在量词块)
形如 的陈述,可以通过把数对 编码为一个字符串 ,改写为 。若原来的两个长度都是 的多项式,则它们合并后的长度也是多项式。这一初等的合并正是归纳中所用的步骤;而把存在量词块与全称量词块交换,则是另一种运算,一般而言是无效的。
常见错误
(有条件的坍缩不是分离)
该定理陈述的是一个蕴含关系。它并没有确立 为假,因为多项式层级是否严格尚属未知。它也没有表明 等于 P。小的非一致电路、一致的多项式时间算法以及层级的坍缩,三者相关但互不相同。
练习与解答
快速检查
(为什么见证前缀语言 属于 NP?)
说明证书是什么。
解答 · 答案
见证提供了 的其余比特。确定型验证者在多项式时间内检查长度、前缀关系以及 。
快速检查
(在搜索构造中,当已知存在扩展时,为什么对以 0 结尾的前缀作一次查询就足以选定下一个比特?)
考虑答案的两种情形。
解答 · 答案
若 0 的扩展具有见证,则选择 0 保持不变式。否则,由于当前前缀至少有一个完整扩展,每个有效扩展都必须以 1 开头;选择 1 保持不变式。
快速检查
(当不存在见证时,搜索电路可以输出什么?)
回想定理保证了什么。
解答 · 答案
任何具有规定输出长度的字符串。仅当存在有效见证时才保证正确性,因此验证者必须检查其结果。
快速检查
(在关键包含关系中,当某个全称选择 没有有效的 时,为什么没有任何被猜测的电路能够通过?)
看看在该特定的 处的检验。
解答 · 答案
在该特定的 处,每个字符串 都使 不成立。电路的输出是这样的一个字符串,因此无论电路描述如何,全称检查都会拒绝。
快速检查
(为什么两个相邻的存在量词块可以合并而不提高层级的级别?)
把数对当作一个字符串。
解答 · 答案
把这两个多项式长度的字符串编码为一个多项式长度的字符串,再让谓词对其解码。这两个存在性选择的先后次序并不引入新的交替。
快速检查
(Karp–Lipton 蕴含关系是否证明了 ?)
PH 坍缩是否已知为假?
解答 · 答案
不能。它说的是该包含关系将蕴含 PH 的坍缩。如果没有独立的证明表明 PH 不会坍缩到第二层,该假设就不能被排除。