有时,检验一个被提出的解远比找到它要快得多。复杂性理论通过简短证书将这一区别形式化,而归约则把一个判定问题的困难性转移到另一个判定问题上。这种转移的方向至关重要:要证明某个目标问题是困难的,就要把已知的困难实例翻译成目标问题的实例。
本单元展开使上述说法变得精确的三个思想。第一,我们通过验证者定义 NP 与 coNP 两个类,并讨论证书能做什么、不能做什么。第二,我们定义多项式时间多一归约,并证明它们能够传递高效算法且可以复合。第三,我们在从 3-SAT 到 CLIQUE 的 NP 完全性论证中使用这些工具,同时考察几种看似有理但并不成立的论证。在全文中,“多项式时间”指确定性图灵(Turing)机(或任何仅带来多项式开销的等价模型)上的多项式时间,所有语言都定义在一个固定的有限字母表上,实例则以合理的方式编码为字符串。
动机:寻找与检验
考虑一个大小为 的数独格。给定一个已填满的格子,检查每一行、每一列和每一宫所需的时间是格子大小的多项式。而从一个部分填写的格子得到填满的格子,看起来需要探索巨大的可能性空间,并且对于推广后的问题,目前还不知道多项式时间的方法。廉价的检验与看似昂贵的搜索之间的这种不对称,正是 NP 类所要分离出来的现象。
这一形式化需要谨慎。“解”必须足够短,以便多项式时间的机器能够读取,否则检验甚至无法查看它。“检验”必须是确定性的且高效的,而且必须是可靠的:任何虚假的证书都不能使它相信一个否定实例是肯定实例。这些要求在下面的定义中都明确出现。
证书与归约
定义 2.1.1
(NP 与 coNP)
若存在多项式 和确定性多项式时间验证者 ,使得 恰好当存在某个长度至多为 的字符串 满足 ,则称语言 属于 。类 由 中语言的补语言构成。对属于 coNP 的语言 ,其否定实例有短的 NP 证书,因为 。这并不声称其肯定实例有短的 NP 证书。每个属于 的语言都同时属于这两个类; 是否成立仍是未解决的问题。
对于 SAT,输入是一个布尔(Boolean)公式,见证是一个真值赋值。对公式求值即可在多项式时间内检验该见证。然而,一个失败的赋值并不能证明不可满足:其他赋值可能是可行的。这一观察并不证明不可满足性没有短证书;那将解决一个重大的未解问题。
仔细阅读定义
定义中有两种量词模式,应当区分开来。对于 ,必须存在一个短的 使得 。对于 ,每一个短的 都必须使 。用符号写出即
对其取否定得到 。因此,补语言由对短字符串的全称条件来描述。这个条件不是一份存在性的证书。属于 的语言则对两种答案都有可高效检验的短证书,分别使用它自身和其补语言的 NP 验证者。
包含关系 成立,是因为 对补运算封闭:将判定器的接受与拒绝结果互换即可。 是否成立同样是未解决的。如果某个 NP 完全语言 属于 coNP,则可推出 。这是归约的一个简洁应用:对 ,归约 同时也是归约 ,而 ,所以由下文证明的 NP 对多项式时间原像的封闭性得 。因此 ,再取补集即得 。
定义 2.1.2
(多一归约与完全性)
多项式时间多一归约 是一个多项式时间可计算的函数 ,满足 当且仅当 。若 中的每个语言都在此意义下归约到语言 ,则称 是 NP 难的。若 既是 NP 难的又属于 ,则称它是 NP 完全的。
“当且仅当”包含两个蕴含,对每个归约都必须证明这两个蕴含。正向蕴含()称为归约的完备性,反向蕴含()称为可靠性;等价地,即 。遗漏任何一个方向都会产生无效的论证,下面的反例将说明这一点。函数 必须是全函数,并且在每个字符串上(包括不是良构实例的字符串)都能在多项式时间内计算;标准约定是,只要 不是所有字符串的集合,就把格式错误的输入映射到 之外的某个固定字符串。
命题 2.1.3
(归约传递高效的判定过程)
若 且 ,则 。多项式时间多一归约是传递的。
证明
(把归约与判定器复合)
对于输入 ,计算 ,然后运行 的多项式时间判定器。成员资格的等价性保证了答案是正确的。 的输出长度至多为其运行时间,因而是 的多项式;将两个多项式界复合后仍是多项式。传递性由复合归约函数并应用同样的长度界得到。
该命题通常以其逆否形式使用:若 且 ,则 。由于目前还不知道任何 NP 完全语言位于 之外,实际的理解是有条件的:若 是 NP 难的且 ,则 是 NP 难的,并且只有当 时 才属于 。
配套的验证者电路与门约束两节证明了 Cook–Levin 构造以及 SAT、3-SAT 的 NP 完全性:先规范短见证,再模拟带时钟的验证者,最后加入保持可满足性的局部门约束。下面的图例题使用其中的 3-SAT 结论作为背景。3-CNF 公式是若干子句的合取,每个子句包含三个文字出现;这里允许重复文字。配套单元也给出了变量互异约定所需的构件。
一个完全性证明
对新语言 的每个 NP 完全性证明都遵循同一个模板,在给出例子之前值得先陈述它。
- 通过描述一个证书和一个多项式时间验证者,证明 。
- 选择一个已知为 NP 难的语言 。
- 定义函数 并证明它可在多项式时间内计算。
- 证明 。
- 证明 。
定义 2.1.4
(CLIQUE 与子句出现图)
CLIQUE 由二元组 构成,其中 是有限简单无向图,且包含一个由 个两两相邻的顶点组成的集合。给定一个含 个子句的 3-CNF 公式,为每个文字出现创建一个顶点。当来自不同子句的两个顶点的文字不互补时,恰好将它们相连。令 。
定理 2.1.5
(3-SAT 归约到 CLIQUE)
对有 个子句的 3-CNF 公式 ,令 为其子句出现图,并设 。则 可满足当且仅当 有 -团,而且 可在多项式时间内计算。由于 CLIQUE 属于 NP,CLIQUE 是 NP 完全的。
证明
(团归约的两个方向)
一个满足赋值会从每个子句中选出一个为真的出现。所选的顶点构成一个 -团:为真的文字不可能相互矛盾。反之,一个 -团在每个子句中至多包含一个顶点,因此在每个子句中恰好有一个。它的文字不含互补对;将它们的变量赋值使所有被选文字为真,其余变量任意赋值。每个子句都被满足。图和 都在多项式时间内构造,这就确立了归约的两个方向。
CLIQUE 属于 NP: 个互异顶点的列表是一个证书,并且可以检查所有顶点对之间是否有边。因此,从 NP 完全的 3-SAT 出发的归约证明了 CLIQUE 是 NP 完全的。从 CLIQUE 到 3-SAT 的归约则给出相反方向的转移,其本身并不能证明 CLIQUE 是困难的。
证明透视
团论证为何成立
有两个细节值得明确说明。第一,同一子句中的顶点从不相邻,因此一个团在每个子句中至多使用一个文字出现。由于目标大小是 ,而子句恰好有 个,鸽巢原理迫使每个子句恰好有一个顶点。没有这一限制,大小为 的团可能在某一个子句中使用多个顶点而完全略去另一个子句,从而不能证明每个子句都被满足。第二,“不互补”恰好是一致性条件:一组文字出现可以由同一个赋值同时置为真,当且仅当它不含一对 。如果同一个文字出现在两个被选的子句中,则同一个赋值使二者都为真,这就是为什么相等的文字要相连。
以下互动使用另一个双子句公式;可把它的文字出现位置选择与下方三子句例子比较。
例题 2.1.6
(归约的一个具体实例)
取 ,含 个子句,并将各出现记为:子句 1 中 ;子句 2 中 ;子句 3 中 。共有 个顶点。在不同子句之间,除互补的对之外所有对都有边。在子句 1 与 2 之间,互补的对是 ()、、、、(),因此有 条边,即 。在子句 1 与 3 之间,互补的对是 ,所以有 条边。在子句 2 与 3 之间,互补的对是 、、,所以有 条边。该图有 条边,且 。
该公式是可满足的:取 为真、 为假。子句 1 通过 为真,子句 2 通过 为真,子句 3 通过 为真。三元组 是一个团: 是一条边(上面已算出), 不互补( 对 ),而 连接相等的文字 。反之,三元组 不是团,因为 是互补对 ;相应地,从子句 1 选 、从子句 2 选 、从子句 3 选 会要求 同时为假和为真。归约在这个实例上的表现与所声称的一致。
例题 2.1.7
(不可满足的公式没有团)
取 ,则 、,图有 个顶点。子句 1 的每个文字都是 ,子句 2 的每个文字都是 ,所以全部 个跨子句的顶点对都互补,不画任何边。-团至少需要一条边,所以不存在,与 不可满足一致。若采用连接互补文字的错误规则,九条边都会出现,见下面的常见错误。
无效的论证与反例
由于归约的方向很容易混淆,具体地看看无效论证是如何失败的会有所帮助。
常见错误
(检验不是搜索)
验证者必须对每个肯定实例接受至少一个短见证,并对每个否定实例拒绝每一个见证。它不需要找到见证。高效地检验一个被提出的解,并不意味着目前已知有高效的方法去找到一个解。
常见错误
(沿错误的方向归约)
假设有人证明了 并由此断言 CLIQUE 是 NP 难的。这并不成立。存在一个从 CLIQUE 到 3-SAT 的翻译,仅说明 CLIQUE 不比 3-SAT 更难。事实上,每个属于 的语言都归约到任何至少包含一个字符串且至少遗漏一个字符串的语言:若 ,且 、,当判定器接受 时令 ,否则令 。特别地,每个属于 的语言都归约到 SAT,但这并未说明关于它的困难性的任何事情。
常见错误
(只证明等价的一个方向)
在团构造的一个有缺陷的变体中,将不同子句的所有顶点相连,包括互补的顶点。满足赋值仍然产生一个 -团,但不可满足的公式 会产生六个顶点,且每个跨子句的顶点对都相邻。由于 ,任何这样的一对都是一个 -团。反向蕴含失败,因此这不是一个归约。
最后一个例子具体地说明了为什么边规则中要出现“不互补”:恰好是它使逆向成立。
若 SAT 属于 coNP,则 NP 与 coNP 相等。这就是为什么人们不相信 SAT 属于 coNP:那将使两个被广泛认为不同的类塌缩。这种相信不是一个定理,这里也没有任何结果证明 。
结合下面的封闭性与传递性,这蕴含:若 是 NP 完全的,且 其中 ,则 是 NP 完全的。这正是一个已确立的困难问题能够催生整个困难问题族的确切含义。
反例模式
容易的问题也可归约到 SAT
错误说法是,只要 就能推出 是 NP 难的。取 ,把每个输入都映到固定的不可满足公式 。这是多项式时间多一归约,因为两边的成员关系始终都不成立;实际上,所有字符串构成的语言不可能归约到空语言:肯定实例的像必须属于空集。要证明目标问题困难,应从已知困难问题出发,归约到该目标。
本章的图问题显式编码所有顶点, 是以二进制表示的非负整数。验证者先拒绝大于顶点数的 ,而不会试图读取过长的证书。格式错误的编码不属于这些语言。
命题 2.1.8
(NP 对多项式时间原像封闭)
若 且 ,则 。把归约与验证者复合即可证明;多项式输出长度界同时控制证书长度。
证明
(把归约与验证者复合)
令 为归约, 为 的验证者及其界。定义 。由于对某个多项式 有 ,长度至多为 的证书就足够了;并且 在多项式时间内运行,因为计算 以及在多项式长度的输入上运行 都是多项式时间的。若 ,则 ,某个短的 被接受;若 ,则 ,每个 都被拒绝。所以 。
例题 2.1.9
(很大的数值阈值不需要很长的证书)
一张显式列出的图有五个顶点,而二进制阈值表示 。它不可能有这么大的团。验证者读取阈值和顶点数后即可拒绝,无须索取一千个标签。若 ,候选列表 会因重复而在检查边之前被拒绝;对 则检查三对顶点。证书验证的是所选集合,并不声称不存在更大的团。
练习与解答
快速检查
(为什么 ?)
从证书的定义开始。
解答 · 答案
验证者可以忽略其证书,直接运行该语言的多项式时间判定器。对于肯定实例,空证书就足够了。
快速检查
(一个归约把 映射到 。若 有多项式时间判定器,可以推出什么?仅仅由 是容易的又不能推出什么?)
先计算,再判定。
解答 · 答案
计算归约,然后判定 ;这就在多项式时间内判定了 。 是容易的并不蕴含 是容易的:归约可能只到达 的实例中容易的一个子集。
快速检查
(在证明 NP 对多项式时间原像封闭时,为什么长度至多为 的证书就足够了?)
先界定 的长度。
解答 · 答案
验证者 作用于 ,而 。取 为非递减的(这不失一般性), 需要的证书长度至多为 。
快速检查
(在从 3-SAT 到 CLIQUE 的归约中,一个公式有 个子句。给出顶点数和边数的最大可能值,并计算 的确切边数。)
数一数互补对。
解答 · 答案
有 个顶点。两个不同子句之间有 个顶点对,且有 对子句,所以至多有 条边,当不存在互补对时取到。对于给定的公式,,所以有 个顶点和 个跨子句的顶点对。互补对有: 一对, 四对(),共五对,所以有 条边。赋值 为真、 为假满足该公式,而 的顶点与第一个 的顶点构成一个 -团。