动机
本章的图归约以三文字子句为起点。为什么这种看似受限的输入能表达任意布尔(Boole)公式?反复使用分配律,可能产生巨大的等价合取范式。多项式归约需要另一种中间结果表示。
核心办法是为每个子公式的值命名,用少量子句约束局部计算,再用最后一个子句要求整个公式为真。下面证明变换保留哪些赋值,特别说明新变量和短子句的作用。
定义
定义 4.2.1
(布尔公式与赋值)
布尔公式是一棵有限有根树,叶子为变量或常量,内部节点为一元否定、二元合取或二元析取。大小 是节点数;同一子公式写两次就占两个子树。赋值为每个出现的变量指定布尔值,并从叶到根计算。
定义 4.2.2
(文字、子句与 3-SAT)
文字是变量或其否定,子句是若干文字出现的析取,CNF 是子句的合取。空子句为假,零个子句的合取为真。本节 3-SAT 要求每个子句恰有三个文字出现,允许变量或文字重复,与配套图归约按出现位置构造的约定一致。
定义 4.2.3
(新变量与赋值扩张性质)
辅助变量必须另取:既不同于原变量,也不同于其他节点或子句的辅助变量。若 使用原变量 和辅助变量 ,称它对 有赋值扩张性质,是指对每个 上的赋值 ,
这不只说明两个公式同时可满足或同时不可满足,还明确了目标满足赋值如何投影回原变量。若任意独立选择辅助值,较大公式并不一定与原公式等价。
定理/命题
定理 4.2.4
(局部门子句强制精确的门值)
以下子句分别等价于所示的布尔等式:
为每个非变量节点命名,加入这些等式,并对常量节点加入单位子句,则每个原赋值恰有一个辅助扩张。再要求根标签为真,便得到原公式的赋值扩张性质。
定理 4.2.5
(到恰三次文字出现的多项式变换)
对有 个节点的公式,门构造后再填充短子句,得到至多 个子句的恰三文字出现 CNF,并保持赋值扩张性质。另一种直接办法把长度 的非空子句,换成使用 个新变量的 个三文字子句,对原变量保持同样性质。空子句与空合取另按下文处理。
定理 4.2.6
(明确起点后的 3-SAT 完全性)
恰三文字出现的 3-SAT 属于 NP。公式变换给出 SAT 到本版本 3-SAT 的多项式时间多对一归约。因此,以 SAT 的标准 NP 完全性为前提,本版本 3-SAT 是 NP 完全的。建立 SAT 起点的计算到公式定理仍是引入的依赖,并未由这里的变换证明。
所引起点可见 Stephen Cook 的官方 P 与 NP 问题说明第2节第5页。下面在本课程内完整证明限制公式形状的这一步。
证明思路
门等式的两个方向都要约束
对每个非变量节点 引入 ,变量叶子保留原标签。常量一加入子句 ,常量零加入 。连接词节点采用上述子句,自己的标签作输出,子节点标签作输入。最后加入只含根标签的单位子句。若公式就是一个变量,根标签就是该变量,只需最后这个子句。
证明
(逻辑门子句算出各节点的值)
AND 门的前两个子句说明 迫使 ,第三个说明 迫使 ,合起来恰好给出合取值,而不是仅有一个蕴含。OR 门的前两个子句使任一输入为一时 必为一,第三个排除输入都零但输出一。NOT 门的两个子句排除输入输出同为零或同为一,只留下相反取值。
给定原赋值,计算整棵树并令每个 等于节点值,便满足全部门和常量子句。反过来,从子节点向父节点归纳,每个满足这些子句的赋值都必须采用相同节点值。因此加入根断言之前辅助扩张唯一;加入之后,当且仅当原根值为一时存在扩张。限制任一目标满足赋值到原变量,也就给出原公式的满足赋值,反方向同样成立。
证明透视
局部一致与全局接受分别需要条件
即使最后结果为假,门子句仍能描述一次真实计算。根单位子句要求这次计算接受。为不同节点分别另取变量,使各处计算可以共存,不会意外把无关值认作同一变量。反方向依赖每个局部等式,不能假设提交证书的人已诚实填写所有辅助标签。
同时控制短子句和长子句
每个门至多给出三个长度不超过三的子句,常量给一个,根断言再给一个。非变量节点至多 个,故总数至多 。把单位子句 换成 ,把二文字子句 换成 。重复文字不改变真假、不增加变量,因而保持扩张性质,并使每个子句恰有三次文字出现。
概念视角组合
把门子句看成被禁止的行
含三个不同变量的子句,在它们的八种赋值中恰好有一种使它为假,所以它禁止那一行。等式 在 的八行中有四行成立,其余四行必须被禁止。子句 禁止行 ;子句 与 合起来禁止 、、 三行。这四行恰好就是不一致的行。
若输入已经是 CNF,可以直接处理长子句。对 ,,引入 ,使用
证明
(子句链保持可扩张性)
原文字全假时,首子句迫使 ,中间子句依次迫使所有后续辅助变量为一,最终子句却为假。原子句至少有一个真文字时,令 当且仅当前 个原文字全假。首子句由此成立。中间子句若 已成立;否则,要么该原文字真,要么下一辅助变量为一。若最后的辅助变量为一,原子句为真便迫使最后两个文字至少一个真。因此全部新子句成立。两端子句加上 个中间子句,共 个; 时中间族为空。
证明透视
为什么辅助变量标记的是一段假文字的前缀
每个辅助变量 都像一面旗,表示前 个原文字全为假。第一个子句在 都为假时把旗升起;每个中间子句把旗传下去,除非下一个原文字为真;最后一个子句在旗传到 之后,要求 之中有一个为真。“原子句为假则不可满足”这个方向只用到旗被一路强制升起。
不显而易见的是另一个方向中 的取法。旗必须在第一个为真的文字之后恰好放下:若把所有 都设为 ,当唯一为真的文字是 时就会失败,因为此时最后的子句中 为假,而 也都为假。证明最后分别检查三种子句形式,这就是两端子句与中间子句要分开处理的原因。
不同原子句使用不同辅助变量,才能组合各自的扩张。长度一、二的子句按前法填充,长度三保持。若原 CNF 含任一空子句,整个公式不可满足,直接输出固定矛盾 。若原来零个子句,则可满足,可以保留为空目标合取。这些边界均是构造的一部分。
归约既要正确,也要有规模界
证明
(多项式规模与属于 NP)
门构造没有用分配律展开子树,而是每节点写常数个子句。设原编码位长为 ,用节点编号命名新变量,并与一致重命名后的原变量区分。每次原变量出现只被复制常数次,新编号用 位,因此目标位长为 。解析、命名和写出都可在多项式时间内完成。直接 CNF 构造在逻辑层面也只与原文字出现次数成线性关系,编码长度仍多项式有界。
格式错误的原字符串送到固定矛盾,使归约对所有输入有定义,而无须先解可满足性。扩张性质给出所需的肯定与否定答案等价。验证 NP 成员关系时,证书为每个不同目标变量提供一位,变量数不超过文字出现数;解析、检查证书长度、计算所有子句都只需输入编码长度的多项式时间。空目标合取用空证书即可接受。成员关系和归约共同把已声明的 SAT 困难性传递到 3-SAT。
例题详解
例题 4.2.7
(沿节点标签计算公式)
对 ,用 、、。门子句分别有三、二、三个,再加根单位子句,共九个,填充前后数量不变。 时唯一扩张为 ,满足根断言。 时唯一扩张为 ,不满足根子句。不能换一组辅助值来修补这个假的原赋值。
例题 4.2.8
(拆分五文字子句)
对 ,使用 、、。在 时,前两个子句迫使 ,末子句因 而成立。若 也变零,五个原文字全假,同样被迫的辅助值就使末子句失败,不存在满足扩张。
例题 4.2.9
(短子句与空子句各有明确含义)
子句 变为 , 变为 。空原子句在公式层面换成上述两个矛盾子句,因为它已使整个合取为假。没有任何子句的 CNF 却为真。把空子句与空子句集合混同,会在应用任何构造前就把答案颠倒。
例题 4.2.10
(扩张不一定总是唯一)
四文字子句 拆成 。若四个原变量全真, 的两个值都可行。链编码保留扩张是否存在,却可能引入多个扩张。完整门编码则有前面证明的唯一性。可满足性归约本身不保证保留满足赋值的数量。
常见错误
反例模式
单向门约束可能接受假的原赋值
对 ,若只用 约束内层标签 ,外层标签 保留正确 NOT 子句并断言 。当 时,选 可满足全部弱化约束,原公式却为假。缺失的子句 恰好排除此错误内层值。每个门都需要完整的等式约束。
常见错误
(不同构件之间重用新变量)
新变量不能在互不相关的构件之间重用。每个原子句或逻辑门都需要自己的辅助变量,这样不同构件各自选取的扩张才互相独立,可以合并在一起。
常见错误
(用分配律展开而不是为子公式命名)
归约需要多项式的输出规模。直接对 用分配律展开,会为“从每一对中各取一个变量”的每种选法产生一个子句,共 个子句。这种展开不能说明归约是多项式的;为每个子公式命名,则每个节点只写常数个子句。
常见错误
(以为三个文字必须是不同的变量)
这里采用的约定是“恰好三个文字出现位置,允许重复”。若要求三个文字来自不同变量,需要另外的构造,本节并未悄悄包含。
总结
新节点标签与完整门等式描述唯一计算,根断言筛选结果为真的计算。重复填充不改变短子句的含义,长析取链保留扩张存在性。多项式编码界与 NP 验证共同完成 SAT 到 3-SAT 的归约,SAT 的起点完全性仍明确作为前提。
练习
快速检查
(分别考虑 与 ,证明 OR 门的三个子句强制 。)
三个子句是 、 与 。
解答 · 答案
时,前两个子句变成 与 ,迫使两个输入都为零;第三个子句已经成立。 时,前两个子句成立,第三个子句要求 。这正是 等于析取的各种情形;反过来,这些情形满足全部子句。
快速检查
(给出 的恰好三个文字出现位置的逻辑门编码,并验证哪些原赋值能扩张为满足的目标赋值。)
把 NOT 节点命名为 ,并在根上断言 。
解答 · 答案
取新标签 及子句 、 和 。 时, 满足它们。 时,NOT 子句迫使 ,与输出子句矛盾,所以没有扩张。重复文字补足长度三,而不改变任何一个蕴涵关系。
练习 4.2.11
(写出六个文字的子句所对应的链。证明原文字全为假时产生矛盾,并说明原子句为真时的满足扩张。)
核心
解答(3)
- 1
写出子句链
、、 以及 。
依据: 时有 个辅助变量和 个子句。
- 2
处理全为假的情形
关键一步
若所有 都为假,第一个子句迫使 ,接着第二个迫使 ,第三个迫使 ,最后的子句 变为假。没有任何扩张能满足这条链。
依据: 每个子句都迫使下一个辅助变量取一。
- 3
处理原子句为真的情形
令 当且仅当 全为假。第一个子句成立,因为 全为假时 。中间子句在 时成立;若 ,则要么 为真,要么 全为假,从而 。若 ,则 都为假,所以原子句中为真的文字是 或 ,最后的子句成立。
快速检查
(某个编码对每个逻辑门都用了正确的子句,却漏掉根节点的断言。它的可满足性能否推出原公式可满足?请给出反例,并说明为什么仅凭子句数目的界不能建立正确的归约。)
试试 。
解答 · 答案
不能。对 ,每个原赋值仍然有对所有节点的如实求值,尽管根的值永远为零。没有根的单位子句时,逻辑门约束是可满足的,而原公式不可满足。多项式规模与语义正确性是两项各自独立的证明责任;要得到所需的对应关系,必须有根的子句。