动机
一个多项式规模的电路可以多次重用同一个中间结果。普通公式是一棵树:如果我们把每个被重用的结果都代换为完整的表达式,就可能不断重复同样的工作。这正是上一单元的验证者电路与小规模可满足性公式之间剩下的障碍。解决办法是给每个中间值命名,并施加一个简短的约束来说明这个名字的含义。
辅助变量并不需要在对新名字的每一种任意赋值下都保持原来的表达式;它们需要保持的是一致扩张的存在性。这一区别是归约的核心。我们先编码各个门,再把长子句拆成三文字子句,并始终追踪对每个新变量的存在量词。结合上一单元的构造,这就证明了 SAT 与 3-SAT 的 Cook–Levin 结论,而不只是引用它们。
定义
定义 2.3.1
(文字、子句,以及语言 SAT 与 3-SAT)
文字是一个变量或其否定。子句是若干文字的析取;合取范式(CNF)公式是若干子句的合取。这里的三 CNF 公式要求每个子句恰有三个文字出现,允许重复。因此 是允许的。若采用要求三个互不相同的变量的约定,则需要下面给出的额外短子句小工具;仅靠文字重复并不能满足那种不同的约定。
我们对使用 AND、OR、NOT 及常量的显式编码布尔(Boolean)公式定义 SAT,对采用刚才所述的三 CNF 约定的公式定义 3-SAT。格式不合法的串是否定实例。两个语言都属于 NP,因为赋值的长度至多等于显式描述的长度,并且可通过对公式求值来检验。空合取为真,空子句为假;我们在给出全函数归约时处理这些情形。
定义 2.3.2
(等可满足性)
两个公式 与 称为等可满足的,如果其中一个有满足赋值恰当另一个也有。我们的变换证明的是更强的逐输入命题
这并不是说对 的每个选择都有 。新变量表示一致的中间值,而不是额外的任意接受许可。
定理/命题
定理 2.3.3
(线性规模的门编码)
对于具有 个输入变量、 个门(由常量、二元 AND/OR 与一元 NOT 构成)的显式编码布尔电路,可以在多项式时间内构造一个 CNF 公式,其每个子句至多有三个文字,至多有 个变量。它至多有 个子句,并且对原输入的每个赋值,当且仅当电路输出一时,该公式有满足的扩张。
定理 2.3.4
(SAT 与 3-SAT 是 NP 完全的)
在上述显式公式编码与重复文字约定之下,SAT 与 3-SAT 是 NP 完全的。此外,每个 CNF 公式都可以在多项式时间内转化为等可满足的三 CNF 公式。对每个需要新变量的门或子句,分别使用新的变量。
证明思路
为门的值命名,而不是复制它的整个过去
证明
(门的关系与一致的值)
给每个门一个自己的输出变量 。它的来源线是已经为输入位或较早门的输出命名的变量。对每种类型施加以下子句:
常量一门有单位子句 ;常量零门有单位子句 。再添加一个单位子句,为指定的输出线命名,要求它为一。如果输出直接是一条输入线,就在最后的子句中使用该输入变量。
每个门的子句表达了其关系的两个方向。对于 AND 门,前两个子句说明 迫使两个输入都为一;第三个说明若两个输入都为一,则 必须为一。对于 OR 门,前两个子句在任一输入为一时迫使 ,而第三个禁止两个输入都为零时 。NOT 子句迫使取相反的值。这些检验对所有布尔输入都证明了这些关系,而不只是针对某个成功的例子。
给定一个输入赋值,对电路求值就为每个门提供了一组一致的值。这些值满足所有定义子句,并且恰当电路接受时才满足最后的单位子句。反过来,对全部变量的任何满足赋值都满足每个门的关系。按拓扑顺序做归纳,迫使每个门变量等于其真实的求值结果。于是最后的单位子句使电路输出为一。事实上,在施加输出为一的要求之前,一致的扩张是唯一的。
每个门至多有一个新变量,至多三个子句,再加上输出子句。每个子句的宽度有界。读取门列表并写出相应的固定模式需要多项式时间,其中包括用作变量名的二进制下标。这一变换通过反复引用共享线的名字来保持共享,而不是反复展开其表达式。
概念视角代数
把门的关系写成二元域上的方程
在 上,三种门的关系就是方程: 对应 , 对应 , 对应 。逐一检查 的八种赋值与 的四种赋值可知,上面每组子句恰在相应方程成立时被满足。于是电路变成一个次数至多为二的方程组,每个门对应一条方程。
用链替换长析取
证明
(以链替换长子句)
对于子句 (),引入互不相同的新变量 ,并把它替换为
当 时中间的合取为空,只剩两个子句。若原来的每个文字都为假,则第一个子句迫使 ,中间的子句依次迫使此后每个 ,而最后一个子句为假。因此链被满足就意味着原文字中至少有一个为真。
反过来,若原子句为真,则当且仅当 全为假时令 。第一个子句由此规则成立。在中间子句里,若 ,其否定已满足该子句;若 ,则下一个文字为真,或者下一个前缀仍为假且 。在最后的子句中,要么其前缀标志为零,要么最后两个文字之一为真。所以该链有满足的扩张。这就证明了逐赋值的存在性等价。
证明透视
链的两个方向各用到什么
链接变量 可以理解为一项义务:前 个文字都已失败,因此后面的文字仍必须满足原子句。两个方向用到的东西不同。可靠方向(链被满足则原子句为真)是一个向前的归纳:若每个 都为假,第一个子句迫使 ,其后每个中间子句 又迫使 ,直至最后一个子句不成立。完备方向按义务规则定义 ,并对每个子句检查一次,分 与 两种情形。不显然之处在于:约束只需容许一致的义务,而不必迫使其唯一,因此可以有多个延拓。同时处理多个子句时,用到的假设是 的全新性:两个子句共用同一个链接变量,可能同时被要求为 与 ,下面的第三个例题正说明这一点。
长度为一或二的子句可通过重复某个文字来补足。空子句使整个输入为假,所以输出一个固定的不可满足三 CNF,例如 。空合取则可改为送到一个固定的重言子句。把格式错误的输入串送到该固定的不可满足公式。长度为 的长子句使用 个新变量和 个新子句。对显式列出的出现求和,除多项式的命名开销之外,新符号的数量是线性的。不同子句之间的新变量互不相同,保证它们的满足扩张可以一起选取。
反例模式
链并非对每个链接值都等于原子句
声称: 的链 对 的每个值都与该子句有相同的真值。取 、,此时子句为真。 时链为真,但 时第二个子句是 ,链便为假。成立的陈述是存在式的:有某个 的取值可行。这就是定义要求 而不是等式的原因。
若要求三个互不相同的变量
另一种常见的约定同样可以做到。先删去子句中文字的重复副本。同时含有某变量及其否定的子句是重言式,可以丢弃。经过这种化简后,子句中不同的文字出现对应不同的底层变量。于是长子句链的每个新子句已有三个互不相同的变量,因为每个链接变量都是新的。
对于双文字子句 ,引入新变量 并使用 。若原子句为真,则无论 取何值,两个子句都成立。若它为假,两个子句要求 同时取两个值,矛盾。对于单位子句 ,使用两个新变量 及四个子句 、、 和 。 为真时全部四个都满足; 为假时,对 的每个赋值都会使其中一个子句为假。这些同样是存在性扩张等价。
空子句可以表示为三个新变量上全部八种三文字符号模式的合取。每个赋值都会使这八个子句之一为假,所以它们的合取不可满足。对于为真的空合取,输出一个可满足的三变量子句。所有这些替换对每个短子句只使用有界个新变量,保持了多项式规模界。因此要求互不相同变量的变体同样是 NP 完全的。规定子句约定使证明变得精确;这些小工具则说明为什么这两种约定具有相同的复杂度分类。
证明
(由电路可满足性得出 NP 完全性)
最后,上一单元已证明 CIRCUIT-SAT 是 NP 完全的。门构造再加上短子句补足,把它归约到 3-SAT。由于 3-SAT 属于 NP,它是 NP 完全的。同样的公式也是普通的布尔公式,所以它们证明 SAT 是困难的,而 SAT 属于 NP。另一种办法是把任意布尔公式看作其语法树电路,并用门构造来编码。两条路线都不会把共享电路展开成可能巨大的树。
例题详解
例题 2.3.5
(编码一个电路并恢复其内部值)
令 ,,输出 。该公式包含三个 AND 子句、两个 NOT 子句、三个 OR 子句和最后的单位子句 ,共九个子句。对输入 ,唯一一致的门值为 ,所以该公式在此输入下可满足。对 ,一致性迫使 ,与输出单位子句矛盾。手工选取 无法绕过 OR 子句。
例题 2.3.6
(五文字子句有两个链接变量)
对于 ,链为
若只有 为真,令 。第一个子句由 满足,第二个由 满足,最后一个由 满足。若五个文字全为假,前两个子句迫使两个链接变量都为一,最后一个子句失败。该构造使用三个子句,恰为 。
例题 2.3.7
(为什么不同的原子句需要不同的链接变量)
考虑 。固定 以及 ,使两个原子句都为真。第一个四文字链迫使其链接变量为一,因为 为假。第二个迫使其链接变量为零,因为 为假。互不相同的新链接变量使两个要求同时成立。若重用同一个链接变量,就会产生矛盾,并错误地拒绝这个满足的原赋值。新变量是正确性的条件,而不只是命名上的偏好。
常见错误
反例模式
每个门只用一个蕴涵是不够的
如果 AND 门 只用 表示,则 满足该子句,尽管门的输出本应为零。随后的输出断言就可能接受一个不可能的计算。必须使用完整的三子句模式;说“门输出蕴涵某个输入为真”比 AND 关系弱。
常见错误
(等可满足并不保持赋值的个数)
等可满足也不同于保持满足赋值的个数。门的定义对每个原输入有唯一一致的扩张,但长子句链可能有多个满足的链接赋值。普通的 NP 困难性只需要保持存在性。计数归约还需要额外的重数论证,不能仅仅因为判定归约成立就加以断言。
常见错误
(这个归约并不求解公式)
这一变换并不求解目标公式。它构造一个规模受控的公式,其赋值在所述的存在意义上与原来对应。之后枚举所有赋值仍可能需要指数时间;NP 完全性并不是多项式时间的可满足性算法。
总结
新名字保持了电路的共享;局部子句强制每个门的精确关系;链接链分配长子句,同时保持扩张的存在性。两个方向与规模界使归约完整。结合验证者到电路的构造,这些论证在所指定的编码下证明了 SAT 与 3-SAT 是 NP 完全的。
练习
快速检查
(写出 的子句,并验证 的情形。)
解答 · 答案
子句为 、 和 。两个输入都为零时,前两个已经为真,最后一个迫使 。因此输入为假的情形并非不受约束。
快速检查
(对八文字子句,链使用多少个新变量和多少个子句?)
解答 · 答案
有 个新变量和 个子句。它们的合取只有十八个文字出现,所以链的长度关于原子句长度是线性的。
快速检查
(对四文字子句 ,给出对原变量的一个赋值,使其新链接变量的两个取值都被允许。这对赋值计数说明了什么?)
解答 · 答案
令 ,。则无论 取何值, 与 都成立。因此一个原赋值有两个扩张。该构造保持可满足性,但不会自动保持其个数。
快速检查
(说明如何处理含有空子句的 CNF 输入,并解释为什么把它映到空合取是错误的。)
解答 · 答案
空子句在每个赋值下都为假,所以整个 CNF 不可满足,必须映到一个固定的不可满足三 CNF。空合取为真;映到它会把否定实例变成肯定实例,破坏归约的反向方向。
这完成了 Trevisan–Williams 讲义中介绍的基于电路的路线。这里给出的显式子句模式与边界约定,使保持可满足性的各项陈述可以直接检验。