动机
计数单元介绍了非一致电路;层级单元介绍了交替量词。本单元研究小型非一致描述能够表达什么,并证明一个独立的多项式层级条件坍缩。这些结果本身不证明把电路假设与层级坍缩联系起来的 Karp–Lipton 定理;该定理在此未加证明。
关于电路的第二个定量结果
一个自然的问题是,非一致性是否使每个语言都有小电路。答案是否定的,一个简短的计数论证说明了原因。我们使用一个明确但粗略的编码界,证明关于不同布尔(Boolean)函数的个数与小电路的个数之比较的一个简洁版本。
命题 8.4.1
(小电路计数与难计算的函数)
固定 与整数 。设基 上每个至多有 个门(不计输入)的电路,通过如下方式描述:对每个门,在三种类型中选择其类型,并从 个输入、两个常量以及更早的门中选择其输入来源,候选至多有 个。则这类电路所计算的不同函数 的个数至多为 。特别地,若 ,则 个比特上存在某个函数,没有至多含 个门的电路。
证明
(证明)
将门 按拓扑序排列。每个门 由其类型(三种选择)以及至多两个输入来源指定,每个来源选自 个输入变量、两个常量 与 以及 个更早的门,这是一个至多有 个候选的集合。对于一元门 ,第二个来源被直接忽略,因此对每个门都计两个来源只会多算。故每个门至多有 种描述,而 个门的序列至多有 种描述。最后指定一个门作为输出,这至多贡献一个因子 。每个至多有 个门的电路(用未使用的门填充较小的电路)在这个集合中都有一个描述,并且此类电路所计算的每个函数都由某个描述所定义的电路计算。所以可计算函数的个数至多等于描述的个数。从 到 的函数恰有 个。若描述的个数严格小于 ,则有某个函数不被任何此类电路计算。
要看出该条件是可以满足的,取 且 。则 ,,且 。所以描述的个数至多为 ,这里用到 。与此同时,。由于 ,在此基下 个比特上的某个函数需要多于 个门。该论证是非构造性的:它证明了困难函数的存在,却没有给出任何一个。
同一估计给出一个不属于 的完整语言,而不只是一个困难的十比特函数。对充分大的 ,取 。电路描述数上界的对数为 ,最终小于 。在每个这样的长度选取字典序最小、未被这些描述计算的真值表 ;对有限多个较短长度任取函数。这些真值表共同定义一个语言。因为 最终超过 的每一个多项式,所以不存在计算该语言的多项式大小电路族。通过枚举寻找第一个缺失真值表可能非常昂贵;这个论证没有给出该语言的多项式时间判定器。
概念视角组合
把电路看成简短描述
依证明,至多有 个门的电路可用至多 个比特写下,而 个输入上的真值表有 个比特。命题说的是同一件事,即鸽笼事实:简短描述比真值表少,所以必有某个真值表没有简短描述。当 、 时,描述数少于 ,而真值表有 个。
建议与多项式规模电路族
电路族允许每个输入长度对应一个不同的有限对象。建议机器(advice machine)以另一种方式表达同样的自由度:一个多项式时间算法接收一个依赖于长度的字符串,而该字符串不必能由长度计算得到。对于给定长度的所有输入,这个字符串是固定的。它不能依赖于具体的输入,并且这同一个算法必须对每个长度都有效。
定义 8.4.2
(多项式建议)
设 为一个语言。若存在确定型多项式时间机器 、多项式 ,以及长度至多为 的字符串 ,使得对每个长度为 的 ,
则称 在建议意义下属于 。
该机器没有义务产生 。这一记号并不断言建议为每个输入解决一个不同的问题;同一个 服务于所有 个长度为 的字符串。
定理 8.4.3
(建议与电路刻画同一个类)
一个语言拥有供确定型多项式时间机器使用的多项式长度建议,当且仅当它拥有一个多项式规模的布尔电路族,即每个输入长度对应一个电路。
证明
(证明)
首先设电路 至多含 个门,其中 为多项式。将 的一个有限描述放入 。每条门记录指明其类型,并按拓扑序给出其输入来源的下标。每个下标使用 位,因此完整的描述长度为多项式。对于输入 ,一台固定的确定型机器读取该描述,并按顺序对各门求值,同时保留它们的布尔值。这需要多项式时间,并产生 。建议不必能被高效构造:描述的存在性即已足够。
反之,设 与 满足建议的定义,且运行时间至多为 ,其中把建议长度计入后 为多项式。一个时间为 的计算只访问多项式数量的带格。用多项式个比特编码其整个有界格局,包括带符号、读写头标记和状态。对于固定的机器,下一格局中每个带格的内容及其读写头标记,由一个常数大小的局部邻域和有限的转移表所决定。因此,一个多项式规模的布尔电路可以把一个格局的编码变换为下一个格局的编码。将 个这样的副本串接起来,对已停机的计算用不变的格局进行填充。初始编码由输入变量和 的固定比特构成;常量把这些建议比特硬连线到电路中。输出门读取最终的接受位。其规模为 的多项式,并且在所有长度为 的输入上判定 。对于较小的长度,则分别选取这有限多个电路。由于并未假设存在产生序列 的算法,所得的电路族不必是一致的(uniform)。
该构造证明的是两种非一致定义的等价性,并未证明 :如果建议总是可以被高效计算,那么它可以在 内部生成,但这里允许任意的建议。反过来,仅仅知道每个单独的输入都有一个简短的有用字符串,就会使该字符串能够接触到输入,而这并不是此处的定义。
反例模式
多项式建议并不使语言可判定
很容易以为带有多项式建议的语言必然可判定,因为每个建议串都是有限对象,而 是普通的算法。这个说法是错的。固定图灵(Turing)机的一个枚举 ,令 。取一比特建议:若 停机则 ,否则 ;并令 恰在 是非空的全 串且 时接受。则 以线性时间运行,,且 恰当 ,所以 。然而 的判定器会判定任一给定的图灵机在空输入上是否停机。每个 都存在,但定义从未要求有算法把它找出来。补救办法是额外假设 可由 在多项式时间内计算;这样得到的语言确实属于 ,见练习。
例题 8.4.4
(对每个长度一次性编码的电路)
对于长度 ,设 使用每个异或的固定常数规模 AND、OR 与 NOT 实现来计算 。其建议可以是由门类型和来源下标组成的一个列表。求值器在全部八个长度为三的输入上接收同一个列表,只有输入比特发生变化。对于 ,电路描述可以是另一个不同的列表。关键在于每个长度都存在这样的列表;这个例子恰好也具有一个简单的一致模式。
例题 8.4.5
(建议是共享的,而不是针对每个输入的答案)
设 恰好包含第一位为 的那些二位字符串。在长度为二时,单门电路 对全部四个字符串都给出正确答案。若有一条所谓的建议规则,对输入 指定单个比特 ,对输入 指定 ,则它其实是在看到输入之后才选择建议。即使每个单独的答案只有一位长,这也不是合法的建议序列 。
例题 8.4.6
(某一长度上的非构造性困难函数)
在 时,前面的电路计数界表明,至多含 个门的电路的描述少于 个,而布尔函数共有 个。因此某个真值表不在该列表中。这并不能指出某个特定的困难函数;而且仅在这一个长度上的下界,也不能排除某个语言存在多项式规模的电路族:渐近的电路复杂度关注的是所有足够大的长度以及一个共同的多项式界。
本单元的两个论证回答不同问题。电路计数表明有些语言没有多项式大小的电路族;条件坍缩则在一致类满足某个相等假设时,涉及层级每一层的所有语言。任何一个结论都不能仅由另一个结论推出。应用坍缩证明时,应在整个归纳中保留其假设:正是该假设提供了从全称量词块到 NP 验证者的转换。后续的 Karp–Lipton 定理有不同的假设,需要此处未展开的额外论证。
坍缩
如果某一层满足 ,则多项式层级坍缩到该层;这一标准定理在此处不加证明地陈述。类似地,当交替量词块的数量不是预先固定时,带量词布尔公式是 PSPACE 完全的;该结果需要另行证明。这两个陈述都没有断言层级各层之间存在已知的严格分离。
尽管这里没有证明一般的坍缩定理,但它的第一个情形有一个简短而完整的证明,展示了其机制。关键的观察是,从 命题中去掉最外层的量词块,会留下一个关于数对的 命题。
命题 8.4.7
(从第一层出发的坍缩)
如果 ,则对每个 有 ,因此 。特别地,如果 ,则 。
证明
(证明)
假设 。我们对 归纳证明 。情形 即定义。设 。由层级单元中的补运算命题,,而由假设这等于 。
设 ,其外层块为长度 的 ,后接以全称块开头的 个交替块,谓词为 。定义
使用一种标准的数对编码,使得 可在多项式时间内从中恢复,并且其长度至少为 。被量化的长度在该数对长度的意义下是多项式有界的,所以这可以由以全称量词开头的 个交替块以及一个多项式时间谓词来描述。因此 。设 是 的一个验证者,使用长度至多为 的证书。则
其中 ;由于数对编码的长度是 的多项式,这个界是 的多项式。数对 是一个多项式长度的证书,可在多项式时间内检查,所以 。因此 ,反向包含由嵌套得出。这就完成了归纳。于是 亦成立,所以每一层都等于 。
如果 ,则 ,因为 对补封闭。第一部分的假设成立,所以 。
证明透视
假设用在哪里
归纳假设 只通过补起作用:它给出 。假设 则恰好只用一次,用来把 读作 。这就是不显然的一步:一个成员资格是全称命题的语言,获得了一个存在式的证书 。一旦有了它,外层的 与新的 就是相邻的存在量词,合并为单个块,于是 个块变成了一个。
有两个细节使论证严谨。数对 的长度是 的多项式,因为 ;否则证书长度界 就无法转化为 的多项式。而没有 的话,归纳假设只给出 ,这并不提供成员资格的简短证书,因此全称块无法去掉。
同样的归纳,在整个过程中把 替换为 ,就是通向一般陈述的标准路线,但该路线需要额外的细节处理,我们在此不予展开。上面的证明还表明了为什么没有已知结果能无条件地迫使坍缩:它恰好利用假设 把一个全称命题转化为一个存在命题,而对于一般的谓词,没有已知的这类转换可用。
常见错误
(坍缩到 NP 并不是坍缩到 P)
该命题假设 ,结论是 。它并没有得出 :目前并不知道 能推出 。只有更强的假设 才给出 。
练习与解答
快速检查
(如果建议机器对长度为 的输入使用 ,它是否可以对该长度的每个输入将 替换为不同的字符串?)
想想建议可以依赖于什么。
解答 · 答案
不可以。建议由长度确定,因此对该长度的每个输入都是相同的。当然,算法在处理这个固定的建议时可以检查输入。
快速检查
(如果一个建议序列本身可以在确定型多项式时间内由 计算得到,证明其语言属于 。)
让机器自己生成建议。
解答 · 答案
对于输入 ,计算 ,由 生成 ,然后在 上模拟建议机器。两个阶段都花费多项式时间,因此它们的复合也是多项式时间。
快速检查
(存在一个需要超过五十个门的十位函数,这是否证明某个被明确给出的语言不属于 ?)
想想计数论证有没有指出缺失的函数,以及它涉及多少个长度。
解答 · 答案
不能。该计数证明并没有指出缺失的真值表;而且它只涉及单个长度和一个固定的门数界。要将某个语言排除在 之外,需要在整个族上排除每一个多项式规模界。