动机
子集和问题询问:一列非负整数中,是否有若干个数恰好相加等于目标值。这个看似简单的算术表述背后,隐藏着对子集的组合搜索。为了证明其困难性,我们用被选中的数来编码一个布尔赋值,并用各自独立的数位列同时检验所有子句。
这一构造依赖于阻止各列之间产生进位。每一列都有固定的目标值和很小的最大可能和,因此可以独立地分析。我们以 3-SAT 的 NP 完全性作为背景知识;该定理在此作为起始结论引用,本节不予证明。
定义
定义 4.4.1
(子集和实例)
子集和问题的一个实例由一个有限的非负整数列表和一个非负目标值组成,所有数均以二进制编码。若存在列表位置的某个子集,其对应的数之和等于目标值,则该实例是 yes 实例。不同位置上数值相等的数是不同的选择。
定义 4.4.2
(3-CNF 公式的十进制列编码)
3-CNF 公式具有明确列出的变量集合 和子句 ,每个子句恰好包含三个文字出现;允许重复出现。对每个变量构造两个数,分别对应取真和取假。使用 个十进制数位:每个变量一列,每个子句一列。变量 的两个数在其自身的变量列上数字为一,在其他变量列上为零。在子句列 中,取真选择数的数字是 在 中出现的次数,取假选择数的数字是 在 中出现的次数。
对每个子句列,再添加两个松弛数,它们在该列的数字分别为一和二,其余列均为零。目标值在每个变量列的数字为一,在每个子句列的数字为四。随后,把这些十进制数转换为二进制编码,作为子集和问题的实例。
定理
定理 4.4.3
(归约的正确性)
所构造的子集和实例有解,当且仅当输入的 3-CNF 公式可满足。
定理 4.4.4
(子集和问题的完全性)
假设 3-SAT 的标准 NP 完全性成立,则子集和问题在多项式时间多一归约下是 NP 完全的。
证明思路或证明
证明
(各列的和都小于十,所以由数位决定相等)
即使任意选取全体数的一个子集,任何一列也不会产生十进制进位。变量列最多接收来自其两个选择数的二。一个子句有三个文字出现,因此在所有被选中的变量数中,它的贡献至多为三;两个松弛数至多再加三。其总和至多为六。因此,等式成立当且仅当每一列的和都等于目标的对应数字。
变量列的目标为一,所以其两个选择数中恰好选中一个。把这些选择解释为一个真值赋值。在每个子句列中,被选中的变量数恰好贡献为真的文字出现次数 。松弛数可以增加 或 ,所以目标四恰好在 时可以达到;当 时无法达到。因此,子集和问题的每个解都给出一个满足赋值。
反过来,按某个满足赋值的规定,选取取真或取假的选择数。每个子句都有 个为真的出现。选取和为 的松弛数,而 属于 。于是所有变量列和子句列都与目标匹配,所选的数之和等于目标值。重复的文字按出现次数计算,同样的推理依然成立。
证明透视
无进位使各列互相独立
“每一列的总和至多为六”这个界用了两次。在正向推导中,它让我们可以对任意子集逐位读出目标整数,而不必事先知道选了哪些数;这正是每个变量列能强制恰好选一个的原因。在反向推导中,它保证由赋值构造的子集确实加起来等于目标。
不显而易见的设计是松弛数 配上目标数字四:它们的子集和 恰好是真出现个数 所需的补数,而对 则不足。若改变进制或目标数字,就必须重新检查这个分离性与无进位的界;没有这个界,进位可能使表面上相符的数位掩盖另一种选择。
证明
(多项式规模与属于 NP)
输出包含 个数,每个数有 个十进制数位,所以它们的二进制长度和构造时间关于显式公式的规模都是多项式的。一个子集就是长度为多项式的证书,并且二进制加法可在多项式时间内验证其和。因此子集和问题属于 NP;从 NP 完全的 3-SAT 出发的归约证明了它是 NP 难的。空公式是可满足的,并被映射到目标为零且没有任何数的实例。格式错误的输入编码可以映射到一个固定的 no 实例,使归约成为全映射。
例题详解
例题 4.4.5
(一个含重复文字的子句)
对于 ,使用两列:先是变量列,然后是子句列。取真数与取假数分别为 和 ;松弛数为 和 ;目标为 。选取真时得到 。选取假时,子句的贡献为零,而两个松弛数加起来只有三,因此无法达到目标。
例题 4.4.6
(一个有两个为真出现的满足子句)
若所选的变量数在某个子句列中贡献 ,则选取数字为二的松弛数。这一列的和于是为四。松弛数的选取可以调整一个已满足的子句,却无法修补一个为真出现次数为零的子句。
例题 4.4.7
(一个有三个为真出现的子句)
若三个出现全为真,则变量的贡献为三,数字为一的松弛数使其达到目标四。加上两个松弛数后可能的最大贡献为六,仍低于十进制的基数。
常见错误
反例模式
没有松弛数的目标可能拒绝一个已满足的子句
如果子句的目标为四,却不提供任何松弛数,那么恰有一个文字为真的子句只贡献一,尽管它已被满足,也无法通过数位检验。松弛数表示当 时所有可能的差值 。
常见错误
(没有“各选一个”的约束就选数)
变量列的约束保证每个变量恰好选一个;只是选出一些看似为真的数并不足够。两个数都不选,该列为零而不是一;两个都选,则该列为二。
常见错误
(只检查由赋值构造的子集)
逆向的证明必须处理任意的子集和解,而不只是由赋值构造的子集,这需要对每个子集都成立的无进位界。子句列计算的也是文字出现的个数,包括重复的出现。
逐列构造这些数
数位只是概念上的标记;先排变量列、后排子句列的固定顺序,给出一个普通的十进制整数。显示时允许有前导零,但它们不改变其数值。一个子句的两个松弛数在其他每一列上都为零,所以它们只影响该子句的总和。同一变量的两个选择在该变量列上相同,但根据各自使哪些文字为真而不同。
例如,若某个子句包含 的两次正出现和另一个变量的一次出现,则 的取真选择数在该子句列的数字为二,其取假选择数在该处为零。若某个子句同时包含 和 ,则取真数与取假数分别记录各自的出现。恰好选取 的一个数,就保证每个出现恰在其文字为真时贡献一。
例题 4.4.8
(两个子句与两个变量)
设 ,。各列按 的顺序书写。 取真与取假的选择数分别为 和 , 取真与取假的选择数分别为 和 。目标为 。选取 时得到 ;在每个子句列上加上数字为二的松弛数,得 。若 为真而 为假,则所选的选择数给出 ;第二个子句列为零,用至多为三的松弛数无法达到四。
只要每个数与目标使用同一顺序,十进制列的顺序就可以任意。把所构造的数转换为二进制,改变的只是它们的表示,而不是数值,也不影响子集和的等式。明确列出变量,可保证 和 受公式表示长度所限制;未使用的已列出变量仍然得到一个选择列。
为什么无进位论证适用于每个子集
逆向的蕴涵必须分析任意的子集和解,而不仅是由赋值构造出的子集。在我们知道每个变量恰好选取一个选择数之前,两个选择数可能都被选中,也可能都未被选中。即便如此,一个变量列至多接收二。在子句列中,每个文字出现恰好出现在其变量的取真或取假选择数之一中。因此选取所有选择数,贡献至多为该子句的三个出现。松弛数至多再加 ,所以每个子句的总和至多为六。
所有数位与数都是非负的。由于每一列的原始总和都小于十,普通十进制加法不会从任何一列产生进位。因此,一个和等于目标整数,当且仅当它的所有列总和都等于各自的目标数字。正是这一论断,使变量列能够强制一个选择,使子句列能够强制满足性。若只对具有赋值形状的子集给出和的界,逆命题的证明就会留下缺口。
概念视角代数
一条整数方程等于每列一条方程
由于没有任何一列进位,这个实例等价于一个以 为未知数的线性方程组,每列一条方程。变量列 的方程为 。子句列 的方程为 ,其中 是被选中的选择数里 的出现次数之和, 表示是否选取两个松弛数。十进制数字只是把所有这些方程打包成一条整数方程。
选取目标数字四,是为了把零个为真的出现与一个、两个或三个为真的出现区分开。松弛数的和构成 。当 时,所需的补数分别为 。当 时,所需的补数为四,而它不可得。这些具体的数并非神圣不变,但换用不同的基数或目标,就需要重新检验这一区分与进位界。
归约方向与证书
该映射以一个公式为输入,产生一个子集和实例。因此,一个假想的多项式时间子集和判定器,只要先应用该映射,就能判定 3-SAT。这正是把 NP 难性从 3-SAT 转移到子集和问题所需的方向。反方向的映射本身并不能证明子集和问题是困难的。
两个解之间的变换是明确的。满足赋值选取每个变量的一个数以及相应的松弛位置。和为目标的子集为每个变量恰好选取一个数;这些选择确定一个满足赋值。这是等可满足性,并不保证在每一种可能的编码约定下,公式的每个赋值恰好对应一个子集。例如,数值相等而列表位置不同的数,仍然是不同的子集选择。
对于 NP 成员性,证书可以是一个指示所选列表位置的位向量。其长度为输入整数的个数。验证器把所选的二进制整数相加,并用多项式时间的整数算术把结果与二进制目标比较。数值本身可能很大,尽管它们的编码很短;关于目标值的多项式时间界则是另一种伪多项式的论断。
规模与边界情形
每个所构造的十进制数至多有 位。由于它小于 ,其二进制长度至多是 的常数倍。共有 个数,每个数位都可以通过扫描明确列出的文字出现而算出。因此,该归约在公式编码的规模上以多项式时间运行,它并不枚举所有赋值。
子句的空合取为真。当既没有变量也没有子句时,该构造产生空列表和目标零;空子集见证这是一个 yes 实例。当有变量而没有子句时,每个变量列要求选取两个选择数之一,公式仍然可满足。一个形式化的全映射还应规定对格式错误的编码的行为。把每个格式错误的字符串映射到一个固定的子集和 no 实例,是一种标准选择,并不影响对合法公式的正确性证明。
这一构造是专门为恰好含三个出现的子句量身定制的。若另一种输入约定允许更短的子句,应先用重复出现来补足每个非空子句,或另做数位分析。空子句为假,可以直接映射到一个固定的 no 实例。这些选择应当明确说明,而不应假设所有 3-SAT 约定都相同。
总结
变量列强制做出真值选择,子句列统计为真的文字出现次数,松弛数位则恰好在每个子句被满足时补满目标。十进制的界防止了进位,使列的论证成为有效的整数和归约。
练习
快速检查
(一个子句列中两个松弛数字的和可能是多少?)
考虑两个松弛数的每个子集。
解答 · 答案
是 ,分别对应不选、只选一、只选二和两个都选。
快速检查
(为什么变量列不会向相邻的列进位?)
数一数有多少个数在该列的数位非零。
解答 · 答案
最多只有两个变量选择数各贡献一,所以该列的和至多为二,小于十。
快速检查
(若一个子句有一个为真的出现,必须选取哪些松弛数字?)
子句列必须达到四。
解答 · 答案
两个松弛数都要选,加上 ,与一个为真的出现一共达到四。
快速检查
(为什么输出长度是输入长度的多项式?)
数一数数的个数和位数。
解答 · 答案
共有 个数,每个数有 个十进制数位;它们的二进制编码总长度是多项式。