动机
贪心与动态规划未能解某问题,本身并未证明问题困难。归约给出更精确比较:若能高效解一个问题,就能高效解另一个。NP 完全性围绕具有短而易验证证书的问题,组织这些比较。它描述最坏情况的多项式时间可解性,并非声称每个小实例都实际上无法求解。
本篇以二进制字符串编码,按输入比特数计时。图明确列出顶点及边,所以编码长度至少为顶点数。非负整数阈值以二进制表示;负阈值字段视为格式错误。格式错误可在解析时拒绝。宣称构造输出大小为多项式时,这些约定不可省略。
定义
定义 4.1.1
(判定问题、P 与 NP)
判定问题用所有是实例构成的语言 表示。若确定性算法对每个输入都在输入长度的多项式时间内停止并判定成员资格,则 在 P。若存在多项式 及确定性多项式时间验证器 ,使
则 在 NP。字符串 称为证书。验证器对其总输入长度为多项式时间;证书长度界保证合法证书的验证成本亦为 的多项式。
每个 P 语言都在 NP:验证器可忽略证书,直接执行判定算法。NP 并非“非多项式”,它包含容易问题;定义既未提供高效找证书的方法,也未要求否实例有短证书。P 是否等于 NP 仍未解决,见 Clay Mathematics Institute。
定义 4.1.2
(多对一归约与完全性)
多项式时间多对一归约 是总定义的多项式时间可计算函数 ,对每个输入均有 当且仅当 。若每个 NP 语言都归约到 ,称 NP 困难;若它还属 NP,则称 NP 完全。
计算归约函数时,不能先假定知道 是否为是实例。等价的两个方向保持是与否答案。把所有来源实例变成容易的是实例并非有效归约,除非来源本来没有否实例。可把来源格式错误的输入送到目标的固定否实例,使函数总定义。
定理 / 命题
定理 4.1.3
(传递算法与困难性)
若 且 ,则 。归约具传递性。因此,若 NP 完全语言 归约到 ,且 ,则 NP 完全。若任何 NP 完全语言在 P,则 P=NP。
定理 4.1.4
(具体的 NP 完全图问题链)
假设标准的 3-SAT NP 完全性,则以下判定问题均 NP 完全:CLIQUE,问是否有至少 个两两相邻顶点;INDEPENDENT SET,问是否有至少 个两两不相邻顶点;VERTEX COVER,问是否有至多 个顶点接触每条边。
外部依赖。 本篇使用但不证明一般计算到公式定理,以及 3-SAT 的 NP 完全性。Stephen Cook 的官方问题说明第二节 陈述此起点。下面归约均完整证明,但不能取代未展开的计算表格证明。3-SAT 是每子句恰有三个文字出现位置的合取式,容许重复;文字指变量或其否定。
证明思路或证明
证明
(算法传递与传递性)
要用 的求解器判定 ,先计算 ,再把输出交给求解器。归约为多项式时间,写出每个比特需要时间,所以输出长度亦为多项式。求解器对输出长度的多项式成本,遂仍是 的多项式。定义中的等价保证答案正确,证明第一断言。
传递性由复合归约函数得到。同一输出长度论证限制第二函数时间,所以复合为多项式且保持等价。若所有 NP 语言归约到 ,再由 归约到 ,传递性使 NP 困难;属 NP 再补上完全性。最后,若某 NP 完全语言在 P,算法传递便使全部 NP 语言在 P,结合 P 包含于 NP 即得相等。
方向至关重要:要证明新目标困难,应把已知困难来源归约到新目标。把目标归约到已知难题,只表示难题求解器可解目标。容易问题也能归约到难题,所以这个方向不能证明目标困难。
从 3-SAT 到 CLIQUE
设公式有 个子句。每个文字出现位置建立一个顶点,保留子句及位置索引,共 顶点。两顶点恰在来自不同子句且文字不互补时连边;不互补指不是同一变量及其否定。相同子句内不连边。要求的团大小设为 。
证明
(满足赋值与大小为 的团互相对应)
若公式可满足,每子句选一个为真的出现位置。任意两个所选文字同时为真,不可能互补,又来自不同子句,所以全部相邻,形成 大小团。
反之,团每子句至多取一点,因同子句无边。至少 点的团于是恰从每子句取一点。所选文字无互补配对,故能一致地指定其变量值令其为真,其余任意。每子句都有所选真文字,公式遂可满足。这证明两个方向,而不只是画一幅看似合理的图。
只有 顶点及至多二次数目的候选边。判断文字名称是否互补,对编码长度为多项式时间,所以整图可在公式长度的多项式时间内写出。若无子句,空合取为真,送到固定是实例,例如一顶点、阈值一的图。格式错误则送到固定否实例,令归约总定义。
CLIQUE 属 NP:若 ,立即拒绝,不尝试读长度 证书;否则证书列出 个互异顶点,检查互异及每对相邻均多项式,证书长度也多项式。大于 的团包含恰 点的团,所以证书符合“至少”版本。结合归约与属 NP,得到完全性,只依赖已明述的 3-SAT 起点。
证明透视
为什么两条连边规则缺一不可
这个图有两条连边规则,各司其职。同一子句内不连边,使团在每个子句中至多取一点,所以大小为 的团必须在每个子句中恰好取一个出现位置;这正好把团转成“每个子句选一个文字”。互补文字之间不连边,则使所选文字相互一致,可以用同一个赋值使它们全部为真。
两条规则都不能去掉。若允许同一子句内连边,大小为 的团可以在某个子句取几个出现位置而在另一个子句一个也不取,那个子句便没有被满足。若把互补文字连起来,团可以同时含有 和 ,而没有任何赋值能使两者皆真。不同子句中同一文字的两个出现位置是相邻的,这没有问题:同时选取它们是一致的。证明最后把所选文字设为真,其余变量任意赋值。
补图与顶点集合补集
补图 保留相同顶点,两个不同顶点恰在 没有边时连边。某集合在 是团,当且仅当在 独立。因此 把 CLIQUE 归约到 INDEPENDENT SET。由顶点明列,构造至多二次数目的边为多项式。列出顶点并检查选中各对无边,证明属 NP。
证明
(独立集与顶点覆盖互为补集)
在同一图内, 独立当且仅当 是顶点覆盖。若 独立,边不可能两端都在 ,所以至少一端在补集;反之,若补集覆盖全部边, 不可能内含边。因此 时,
得到归约 。若 ,来源为否,可送到只有一边且覆盖预算零的固定否实例。顶点覆盖证书列出不超预算的顶点,再检查每边有被列端点。若预算至少 ,自动为是,所以数值预算大也不会要求超多项式证书。这完成顶点覆盖的成员及困难性证明。
两次“补”不同:一次改变图边,另一次保持图而改变选中子集。把操作分开写可防止常见错误归约。
判定、搜索与最优化
判定预言机只答是或否,搜索则要求证书。对 CLIQUE,可用多项式次判定调用找团。先问大小 是否可行。若是且 ,考虑某顶点 。若删 后仍有 团,便删除并继续;否则每个 团都用 ,输出 ,把图限制在其邻点,所需大小减一。后者成立是因为团的其余顶点都必与 相邻。每步移去至少一顶点或降低需求,保持是实例,所以只作多项式次、不增大图的调用。
这是自适应预言机算法,不是前面一次输出实例的多对一归约;用途也不同,它说明假设有多项式判定算法,此问题便有多项式搜索算法。求最大团大小可先在零到 间对单调阈值作二分搜索,再重建该大小团。这些关系需要证明,不能按定义把判定与最优化混用。
例题详解
例题 4.1.5
(选取一致文字的位置)
取子句 与 。有六个位置顶点,重复的 各有独立顶点。赋值 可选第一子句的 与第二子句的 ,它们相连。若改选 与 ,则没有边。子句归属是构造一部分,所以重复名称不合并顶点。
例题 4.1.6
(独立集及其覆盖)
四顶点路径边为 ,集合 独立,其补集 覆盖每边。 由内含边 而不独立,其补集 也未覆盖该边。这以明确可行与不可行选择验证集合补集等价。
例题 4.1.7
(伪多项式表没有解决 P 与 NP)
前篇背包表对每个数值容量设一状态。具有 比特的二进制容量可接近 ,所以 可对输入长度为指数。找到此表并未自动给出二进制判定问题的多项式算法。关键是编码区分,并非动态规划与困难性归约互相矛盾。
常见错误
反例模式
简单的来源问题不会使目标问题变简单
声称:若 而 CLIQUE 是 NP 完全的,则 是 NP 困难的。取 。把每个输入都映成只有一个顶点、阈值为 的固定图(这是 CLIQUE 的“否”实例),就是一个多项式时间多对一归约 。可是 不是 NP 困难的:NP 含有全体字符串的语言 ,而由它到 的归约 需要对每个 都有 ,这是不可能的。箭头把算法上的用处倒过来传递:快速的目标求解器能帮助来源问题,而快速的来源求解器并不能解任意的目标输入。要证明困难性,应把已知困难的问题归约到目标问题。
常见错误
(NP 完全性证明漏掉一项要求)
困难性证明须有明确映射、多项式构造及输出界、正确性两方向,以及已知难的起点。NP 完全性另须属 NP。只列看似合理的证书而不限制多项式长度,仍有缺口。
常见错误
(把 NP 完全性解读得过头)
不可推断所有 NP 问题均 NP 完全、NP 困难即属 NP,或 NP 完全性已证 P 不等于 NP。它建立的是条件结论:多项式求解器会使 P=NP;也不自动给出指数下界,不保证某实际实例难。近似质量及特殊图类别需要另行分析。
总结
NP 描述有界验证,归约传递假设算法及困难性。从 3-SAT 到 CLIQUE、补图独立集、集合补集顶点覆盖的完整链,逐项展示证明责任。计算到公式定理仍是已明述依赖,没有把省略的一般证明或未解下界当成已建立。
练习
快速检查
(学生证明了 ( 是 NP 完全的),便宣称 是 NP 困难的。请以一个简单的来源语言说明其中的漏洞。)
想一想哪个问题的求解器能帮助哪个问题。
解答 · 答案
这个归约把 的求解器传到 ,并没有证明 困难。例如空语言可以归约到 CLIQUE(永远输出一个固定的“否”实例),但空语言本来就可以立刻判定。要证明困难性,应把已知 NP 困难的语言归约到 。
练习 4.1.8
(证明当阈值以二进制书写(包括阈值超过顶点数的情况)时,CLIQUE 仍属于 NP。)
核心证明
解答(4)
- 1
解析并比较阈值
解析二进制阈值 ,并在多项式时间内把它与顶点数 比较。若 便拒绝,不需要证书。
依据: 两个数都写在输入中。
- 2
定义证书
关键一步
对 ,证书列出 个互不相同的顶点编号,需要 个比特。对 ,空证书有效。
依据: 当 时,列表很短。
- 3
检查证书
所列顶点是否互不相同、是否两两相邻,都可在多项式时间内检查。
- 4
把证书对应到判定问题
∎大小大于 的团必含大小恰为 的团,所以接受证书存在,当且仅当图中有至少 个顶点的团。
快速检查
(对 ,描述归约所得的图,并说明它为什么没有大小为二的团。)
检查哪些出现位置之间有边。
解答 · 答案
每个子句有三个出现位置顶点,子句内没有边。所有跨子句的配对都是互补的,所以也没有跨子句边。这个图是六个孤立顶点,任何两个顶点都不构成团。公式确实不可满足,因为它要求 与其否定同时为真。
练习 4.1.9
(证明:若 且 ,则 。)
核心证明
解答(3)
- 1
应用归约
设 为该归约。对输入 ,在多项式时间内计算 ;它的长度至多为 ,其中 为某个多项式。
- 2
重用 的验证器
关键一步
设 (取为不减)与 为 的证书长度界与验证器。定义 ,并只接受 的证书;这个界至多为 ,是 的多项式。
依据: 的证书长度界用在像 上,而 的长度是 的多项式。
- 3
检查正确性与运行时间
∎验证器 以多项式时间运行。由归约的等价性, 当且仅当 ,当且仅当存在 的证书 使 接受,也就是存在某个短证书 使 接受。所以 。