一段程序跑得慢，只能说明这段程序在当前输入上的表现，不能证明问题本身必须如此。计算复杂性需要先固定问题、编码与计算模型，再说明算法能做到什么，或者一个已知困难问题怎样转换成它。

本篇用3SAT到CLIQUE的具体转换说明归约方向和双向证明，再用0/1背包解释为什么O(nW)的动态规划不一定是关于输入长度的多项式算法。27篇的二分图匹配依然可以高效求解；不能因为另一个图问题困难，就把困难性迁移到所有图算法。

P与NP先讨论判定问题

判定问题对每个合法输入只回答是或否。例如，CLIQUE问“给定无向简单图G和整数k，是否存在至少k个两两相邻的顶点”；优化版本则要求找出最大团。这两个问题有关，但定义类别时不能省略判定门槛。

把完整输入编码成有限二进制串，长度记为L。P包含能由确定性算法在L的多项式时间内判定的问题。NP用证书刻画判定问题。是实例存在长度不超过某个多项式p(L)的证书，确定性验证器能在多项式时间内接受它；否实例不存在任何能被接受的合法证书。

对CLIQUE，证书是k个不同顶点的编号。检查编号范围、不同性以及每对之间有边，就能验证。使用邻接矩阵时需O(k²)次查边，建矩阵或读输入的成本另计；这并不提供一个在多项式时间内找到证书的算法。

NP不是“非多项式”的缩写，也不意味着已证明所有实例都难。P包含在NP中，因为能直接求解时验证器可以不依赖额外证书。P是否等于NP仍是未解决问题；后面的归约不会单独解决它。

归约把哪个问题交给哪个求解器

多项式时间多一归约A≤p B，要求一个可在输入长度多项式时间内计算的映射f，使x属于A当且仅当f(x)属于B。若有B的多项式求解器，先构造f(x)再调用它，就能求解A。

因此要把已知困难性传给B，应该从已知困难的A归约到B。反过来证明B≤p A，只说明B可借助A求解，不足以证明B也困难。比如把一个容易问题交给强大的SAT求解器，不会使原问题突然变成NP难。

NP难表示NP中每个问题都能多项式归约到该问题；NP完全还要求它属于NP。本文引用3SAT的NP完全性作为已有定理，完整证明下面这条归约，不冒称从头证明Cook–Levin定理。

每个文字出现建立一个顶点

3SAT输入是m个子句的合取，每个子句含三个文字；文字是某个布尔变量或其否定。子句内部是“或”，子句之间是“且”。允许同一文字重复出现，也允许一个子句同时含某变量及其否定。

为每个文字出现建立一个独立顶点，记录它来自哪个子句以及带符号变量编号。仅当两个顶点来自不同子句、且文字不是互相否定时连边。目标团大小设为k=m。

共有3m个顶点，至多9m(m−1)/2条候选跨子句边；逐对检查可在O(m²)次编号比较内完成，输出空间O(m²)。变量编号的位长还影响比较与编码成本，但总转换长度仍是原公式编码长度的多项式。它不是一个把指数规模答案藏进输出的转换。

重复文字必须保留各自出现位置。若直接把相同文字合并成一个顶点，多个子句可能需要同一个真文字来满足，而团又不能重复使用顶点，会破坏下面的对应关系。

从满足赋值得到团

若公式可满足，从每个子句选择一个在该赋值下为真的文字出现。选出的m个顶点分别来自不同子句；任何两者不可能互相否定，因为同一赋值不能同时使x和非x为真。因此这些顶点两两相邻，构成大小m的团。

这个方向证明SAT是实例一定映射成CLIQUE是实例。若只完成这个方向，否实例仍可能错误地变成是实例，归约尚未成立。

从团恢复满足赋值

同一个子句的顶点之间没有边，所以一个团至多从每个子句选一个顶点。大小m的团必须恰好从每个子句选一个；更大的团不可能存在，因此“至少m”与“恰好m”在构造图上等价。

团中任意两顶点有边，所以所选文字不会要求同一变量同时为真和为假。把选中正文字的变量设真，选中负文字的变量设假；未涉及的变量任意赋值。每个子句都有一个选中的真文字，公式于是满足。

空公式m=0是可满足的，映射为空图和k=0，空团同样合法。变量只需为实际出现的编号提供赋值；未使用的巨大编号上界不应被误算成必须交付指数长证书的理由。

两个容易写错的构造

若遗漏“不能互相否定”的限制，公式(x∨x∨x)且(非x∨非x∨非x)本来不可满足，构造图却会出现跨子句的二元团。此时图只反映“选自不同子句”，没有保存变量的一致性。

若允许同一子句内部连边，大小m的团可能集中在少数子句中，无法保证每个子句都获得一个真文字。这两条边规则分别承担一致性与覆盖全部子句的职责，不能把它们当作实现细节随意删掉。

由3SAT的NP完全性与本归约，CLIQUE是NP难；再结合前述验证器，CLIQUE属于NP，从而是NP完全。结论是类别关系，不是所有团实例必须运行指数时间的逐实例定理，也不是无条件排除未来多项式算法。

背包DP为何没有消除困难性

给定n个物品，每个有非负整数重量w_i、整数价值v_i以及非负整数容量W，物品至多选一次。空方案合法，负价值物品可以不选。用D_i[c]表示前i个物品在容量不超过c时的最大价值，转移比较不选和选一次两种情况。

沿22篇的状态方法，转移涉及n(W+1)个格，单位成本算术下转移时间O(n(W+1))，初始化另需O(W+1)，总时间O((n+1)(W+1))，滚动数组空间O(W+1)。一维实现按容量递减更新，避免当前物品刚产生的值再次被使用。零重量物品也只处理一轮，每个容量格至多加入一次该物品价值；这不是允许无限次选择。

若W用二进制编码，它只占Θ(log(W+2))位。W=2^b时，容量维却有2^b+1个状态。因此这个运行界关于数值W是多项式，关于W的编码位数却可能指数增长，称为伪多项式时间。还需计入价值加法与比较的位成本，不能把任意大整数都当作常数时间机器字。

若容量本来很小，这个DP仍然可以很好用。困难性分类不否定受限参数、特定分布或小规模实例的有效算法；它要求把“对所有输入的多项式保证”和“在当前参数下可计算”分开。

可复跑检查

教学代码位于examples/advanced-algorithms/sat_clique.py，接口sat_to_clique(nvars, clauses)返回文字出现列表、无向边列表和目标团大小。文字用非零带符号整数表示；knapsack(values, weights, capacity)返回最大价值，不恢复物品集合。

在仓库根目录执行：

1
python3 examples/advanced-algorithms/check_sat_clique.py

本轮实际检查4235个穷举公式、16791个赋值和62619个团候选子集；另有固定种子20260920的100个随机公式。检查器分别枚举布尔赋值和顶点子集，核对两个方向的见证，而不是调用另一份同样的归约实现来充当答案。

背包另检查3280个实例、24700个物品子集，覆盖空输入、零重量、负价值与零容量；非法输入拒绝共8项。结果保存于writing-plans/advanced-algorithms/evidence/sat-clique-results.json。这些是有限范围的教学实现检查；一般归约正确性来自前面的双向论证，不来自枚举数量。

练习

  1. 对含两个子句的公式手工建立文字出现图。分别删除跨子句限制和互相否定限制，给出导致双向对应失败的具体公式。
  2. 一个算法声称用O(nW)时间解决二进制编码背包，因此证明P=NP。指出推理中缺少的输入长度关系；若W≤n²，运行界又应怎样表述？

参考资料