动机
先前的归约都从一个已知困难的问题出发。只有当某一个问题与 NP 中的每一个语言都建立了联系之后,这种做法才有意义。现在我们来构造这种联系。给定一个固定的高效验证者和一个具体的输入,我们构造一个电路,它剩余的输入位就是所提议的证书。当且仅当存在某个证书能使验证者接受时,该电路可以输出一。
这一构造不能只停留在“计算机由逻辑门构成”的说法上。电路的描述必须具有多项式长度,必须有算法能在多项式时间内生成它,并且对其输入线的每一种赋值都必须有明确的含义。我们将仔细交代带子窗口、时钟、短证书与已停机计算。这些细节说明了为什么可以表示整个计算,而无需列出指数多个可能的证书。
本单元证明电路可满足性是 NP 完全的。配套的“门约束”单元把电路转化为一个小的布尔(Boolean)公式,并完成关于 SAT 与 3-SAT 的结论。
定义
定义 2.2.1
(布尔电路与 CIRCUIT-SAT)
布尔电路是一个有限有向无环图,其中明确列出输入顶点、常量门、二元 AND/OR 门和一元 NOT 门,并指定一条输出线。一个门可以为多个后续门提供输入。编码中列出各门的类型和来源下标,因此输入变量的个数至多等于描述的长度。格式不合法的描述不属于 CIRCUIT-SAT。借助拓扑排序,可以在多项式时间内对给定赋值求值。CIRCUIT-SAT 问的是:是否存在某个赋值使指定输出为一。
定义 2.2.2
(规范化的证书格式)
固定一个语言 、一个确定性验证者 以及证书长度的显式多项式界 。我们可以使用证书长度仅依赖于 的固定长度验证者。令
长度为 的证书由一个 位整数 和随后的 个载荷位组成。若 则拒绝;否则把前 个载荷位交给 ,其余忽略。原来的每个短证书都可以表示出来,而新证书被接受时就给出一个被接受的原证书。当 时,头部和载荷都为空,它们表示唯一的空证书。
把规范化后的验证者记为 。采用确定性单带机,具有固定的有限字母表、双向无限的带子,读写头可向左、向右移动或保持不动。其初始带内容为 ,其中 是分隔符, 恰有 位。这是我们证明中使用的验证者模型;标准机器模型之间的多项式模拟是其通常的机器无关解释的背景知识。固定一个已知的多项式时钟 ,它界定 在这类输入上的每一次计算(包括格式错误的证书头部),并将其放大使得 ,其中 是初始非空白串的长度。
令接受状态与拒绝状态为吸收态:它们保持相同的状态、被扫描符号和读写头位置。于是恰好运行 步与提前停机给出相同的答案。可满足赋值不允许选择时钟或机器。
定理/命题
定理 2.2.3
(有界验证者具有多项式规模的电路)
对于上述固定的规范化验证者和时钟,可以由 构造一个具有 个输入变量的电路 ,使得
该电路有 个门,并且可以在多项式时间内构造。其中隐含的常数依赖于所固定的机器,而不依赖于 或 。
定理 2.2.4
(电路可满足性是 NP 完全的)
CIRCUIT-SAT 属于 NP,并且 NP 中的每个语言都有到它的确定性多项式时间多一归约。该归约把 映到电路 ,而不是映到某个被猜出的接受计算。
证明思路
有限窗口就足够
证明
(为何有限窗口已经足够)
记 ,。在时刻 ,读写头与其起始位置零的距离至多为 。我们表示从 到 (含两端)的带子位置。这个窗口有 个单元,包含整个初始串,并在两侧留有空白缓冲。在被模拟的 步移动中,读写头永远不会到达端点。把端点之外的邻居视为空白;这一约定不会影响这里所表示的真实计算。
令 为带字母表, 为状态集。单元标记要么是普通符号 ,要么是带标记的符号 ,表示读写头在该单元上且处于状态 。合法格局恰有一个带标记的单元。标记字母表 是固定有限的。用固定的单射把每个标记编码为 位。没有分配给标记的编码将以任意默认输出处理,使每个电路门计算的都是全函数。
为什么三格邻域决定下一个单元
证明
(三格规则是一个固定电路)
对于合法格局,位置 的下一个标记只依赖于位置 。若读写头在 ,其转移写入一个符号,并保留或去掉那里的标记。若读写头在 且向右移动,它的新状态标记 处已有的符号。读写头在 向左移动时情形类似。若没有读写头进入且中心单元未被标记,则其符号保持不变。更远的读写头一步之内无法到达 。
因此存在一个固定函数 ,它在合法格局中出现的每个邻域上与机器一致。其余的三元组可给定任意固定输出,例如空白标记。我们并不声称任意一组带标记的单元都描述一个计算;进入模拟的只有合法的初始格局。
的每个输出位都是 位的布尔函数。它可用真值表构造:对每个使其输出为一的输入模式,构成刻画该模式的合取式,再取这些合取式的析取。把任何宽的合取/析取替换为二元门。至多有 个模式,由于 固定,这是一个常数。因此更新一个单元只需常数个门。更新整个窗口需要 个门。
概念视角组合
把计算看成由单元标签组成的表
把各层写成一个有 行、 列的表:第 行列出 步之后的各单元标签。三格规则说明,表项 就是 作用于表项 。因此, 接受 ,恰好当以初始纸带开头、逐行套用这条规则的表,其最后一行含有接受标签。
搭建各层并读出接受
证明
(分层、归纳与接受)
初始层包含 、分隔符、空白以及初始读写头/状态的常量。每个载荷位或头部位都是电路输入。其带符号编码的某个固定位,取决于符号零与一所选的编码,它或者是常量,或者是该输入位,或者是其否定。因此这一层可以显式构造,需要 个门;赋值不能再任意选择多位字母表。
把窗口更新电路复制 份并依次组合,把每一层连到下一层。我们对 作归纳:对证书线的每一种赋值,第 层都编码 在 步之后的格局。第 层按构造就是初始格局。若第 层编码真实格局,则每个单元的邻域都是合法的,固定函数 给出真实的下一个标记,所以第 层编码 步之后的格局。因此最后一层就是真实的时刻 的格局。在每个单元处检验其标记是否带有接受状态,并对这些检验取或。恰有一个读写头,所以输出为一当且仅当接受。吸收的停机状态保证提前的接受在最后一层仍然可见。
门的总数为 。为输出描述,遍历层号与单元号,写出固定的局部门模式,其来源下标指向前一层。机器的转移表和局部真值表的规模是常数。下标只需要 位,所以整个描述具有多项式长度并可在多项式时间内生成。构造过程中没有求解任何实例,也没有猜测任何证书。
证明透视
归纳的两个部分各用到什么
归纳有基始步和递推步,两者用到不同的假设。基始步只通过 的各位使用自由线:无论赋值如何,初始层都恰有一个带标记的单元和一个格式正确的带内容,所以时刻 的合法性是自动成立的。递推步在合法邻域上使用三格规则,固定的机器和有界的窗口在这里起作用:读写头永远不会到达端点,而且 的规模是常数。归纳避免了任何关于任意位数组的断言。我们从不声称满足若干局部条件的某一层就是整体合法的;合法性是从初始层继承而来的。只看最后一层就足以判断接受,是因为停机状态是吸收的;规模界则是 层乘以 个单元,每个单元的代价是常数。
接下来由这个构造读出 NP 完全性的两个部分。
成员资格与困难性
证明
(成员资格与困难性)
最后,CIRCUIT-SAT 属于 NP:证书给出其显式列出的输入位的赋值,求值即验证输出。关于困难性,固定任意 及其验证者。该构造给出
这就是所要求的成员资格等价。规范化与电路构造都是多项式的,所以归约是多项式的。不同的语言可以使用不同的固定验证者和时钟;完全性并不要求对所有语言存在一个通用的常数大小的电路。
例题详解
例题 2.2.5
(在不改变问题的前提下表示较短的证书)
设原证书长度界为 。则 ,规范化后的长度为八。要表示原证书 ,取头部 ,后接载荷 。规范化验证者读到长度二,只把 交给原验证者。把最后三个载荷位换掉不会改变任何结果。头部 编码六,无论其载荷如何都必须被拒绝。填充并不意味着任意的尾随位是原证书的一部分。
例题 2.2.6
(读写头进入邻居的单元)
设某个转移为 。中心被标记为 的邻域失去该标记,并得到普通符号零。紧邻其右侧的单元,若此前含有普通符号 ,则变为 。它的带符号并没有被零覆盖:零是写在原来读写头所在位置的。例如,相邻标记 变为 。三格规则所记录的正是这一细微区别。
例题 2.2.7
(时钟估计就是规模估计)
取一个玩具输入窗口长度 ,时钟 。所选位置从 到 ,共得到 个单元块。二十个更新层需要 次局部块更新。若一次块更新使用固定的 个门,则这一部分电路至多使用 个门。这并不是对可能的带子或证书的计数;它统计的是一次可重复使用的模拟中的显式操作。让 以二次方增长,规模界随之增长,而依赖于机器的 保持不变。
常见错误
常见错误
(把常数当成自由参数)
字母表和状态集之所以是常数,只是因为验证者在归约开始之前就已固定。如果机器的描述本身是可变输入的一部分,把它全部藏进常数的规模估计就是无效的。
常见错误
(由机器描述推断时钟)
同样,时钟是一个指定的多项式界,由证明该验证者在多项式时间内运行的论证所提供。我们并不是声称存在一个能从任意机器描述推断出运行时间界的算法。
下面的断言听起来无伤大雅,但在一台具体的机器上会失败。
反例模式
取消吸收约定
断言:更新函数 只需遵循转移表,所以停机状态不需要规则。取一个一步之后进入接受状态 的验证者,时钟 。在时刻 ,带标记的单元是 。转移表中没有这个标记的条目,于是 返回默认的空白标记,标记就消失了。在时刻 没有任何单元带接受状态,最后的检验输出 ,电路便拒绝了 本来接受的输入。断言不成立。修正:令接受与拒绝状态为吸收态,使 把 映到自身;于是接受标记在时刻 仍然存在,最后的检验输出 。
常见错误
(把电路误当成公式)
这个电路还不是普通的公式。一个门可以向多个后继提供输入,每次都复制它的全部计算可能导致指数级增长。下一单元引入辅助变量,在产生公式的同时保持这种共享。仅仅因为模拟有多项式个门,并不能为把其输出朴素地展开成多项式大小的公式提供依据。
总结
规范化证书长度,固定多项式时钟,编码合法的初始带,再分层模拟局部更新。带子窗口与局部字母表给出多项式的门数,显式下标则给出多项式时间的构造器。自由的输入线表示证书,因此电路可满足性恰好刻画了高效的存在性验证。
练习
快速检查
(原证书长度界为七时,求头部长度与规范化证书总长度。空证书如何表示?)
先计算 。
解答 · 答案
头部长度为 ,总长度为十。头部 指明空的原证书;七个载荷位被忽略。每个三位头部现在都描述从零到七的一个容许长度。
快速检查
(为什么无效的单元编码可以获得任意的更新值而不破坏归约?)
想想哪些格局真的会出现。
解答 · 答案
每个证书赋值都产生有效的初始标记。归纳法表明此后每个标记都是机器的真实标记,因为局部函数在合法格局上与转移规则一致。那些任意取值的情形永远不会出现。如果我们转而允许任意的初始格局,这一论证就不再适用。
快速检查
(设初始串长度为 ,时钟为 。共表示多少个单元,使用多少次局部更新?)
使用 。
解答 · 答案
共有 个单元,十五层给出 次局部更新。完整的门数统计中仍须计入每次更新的常数门代价以及最后的接受检验。
快速检查
(说明为什么找到一个使 输出零的赋值并不能证明 。)
比较成员资格中的量词。
解答 · 答案
该赋值只表明某一个所提议的证书失败。成员资格问的是是否存在某个赋值被接受。要证明不属于,就必须证明每个可能的赋值都失败;归约并不把这个全称命题归约为一次失败的尝试。
Trevisan–Williams 的电路证明提供了一个可以互补参照的材料。这里明确规定了有限的带子缓冲和证书长度约定,使该归约可以当作一个算法来理解。