P和NP：为什么答案好检查，却可能不好找？

你给配送系统提了一个看起来不算过分的要求：

“这些地方都要送到，最后回到出发点，总路程别超过预算。”

系统想了很久，没交出路线。

这时同事递过来一张清单：“按这个顺序走，试试。”

你核对地点有没有遗漏、有没有重复，最后把各段距离加起来，很快就检查完了。

奇怪：检查起来这么容易，找出来怎么会那么费劲？

更奇怪的是，如果你把“别超过预算”换成“保证是所有路线里最短的”，即使同事给出了路线，核对工作也突然不一样了：算出它多长，不等于证明没有更短的。

P、NP、NP-Hard、NPC 讨论的，就是这类差别。这是这个系列的入门篇：先把四个名字和它们之间的箭头弄明白，再看工程上能怎么办。

但先记住一句底线：我们还没有证明“容易检查”与“容易求解”一定是两回事。P 是否等于 NP，至今仍是未解决的问题。克雷数学研究所的官方问题页将其列为未解难题。

一、先别背缩写：从五枚硬币开始

桌上有五枚硬币，面值分别是：

3、5、6、9、12。每枚最多用一次，能不能恰好凑出 17？

这里没有无限枚一元硬币可用，也不能把同一枚硬币重复拿两次。

如果别人递来“第 2 枚和第 5 枚”，我们一加：5＋12＝17，检查通过。

如果别人递来“第 1、3、4 枚”，一加：3＋6＋9＝18，检查失败。但这只能说明这份组合不对，不能说明不存在正确组合。

图 1：先读输入，再看别人交来的硬币编号，最后核对“合法、不重复、总和正确”。这份编号清单叫证书。图中两份证书都逐项算过；找到一份有效证书就能确认“有”，一份无效证书却不能确认“没有”。

这叫子集和问题：给定一组非负整数和一个目标，问有没有一个子集恰好达到目标。

五枚硬币，每枚都有“选／不选”两种选择，共有 2⁵＝32 个候选子集。五枚当然不难，但把数量放大，就会发生很不一样的事。

图 2：从上往下看物品数，再读候选数怎样翻倍。假设每秒能检查十亿个候选，30 个物品约需 1.07 秒，60 个约需 36.5 年，100 个约需 4.02×10¹³ 年。这里刻意忽略单次检查成本，只是完整穷举的乐观算账；不是实测，也不是证明任何算法都必须花这么久。

候选太多，只说明一种朴素算法可能很慢，不说明问题已经被证明“无论怎样都得穷举”。聪明算法有时能绕开枚举。P 与 NP 的难点，恰恰是有没有这样的通用办法，而不是“电脑每秒能试多少次”。

康奈尔大学的子集和讲义既证明了这个问题属于 NP，也讨论了它的 NP 完全性与动态规划算法。我们会在后面回到这份看似矛盾的组合。

二、这里的“快”，不是三秒钟，而是怎样随输入增长

复杂性理论通常先把问题写成判定问题，也就是只回答“是／否”。

例如，不直接问“最短路线是什么”，而问：

给定地点、各段距离和预算 X，是否存在一条每个地点恰好访问一次、回到起点、总长度不超过 X 的路线？

X 是输入的一部分。这才是本文所说的旅行商判定问题。

接着，我们要量清输入长度。它不是只数城市、物品或变量，还要算写下距离、重量、容量这些数值用了多少位。

多项式时间，大致是运行步数被输入长度的某个固定次幂控制住，例如平方、立方；指数增长则像“每多一个选择，就翻一倍”。

这里有两个容易误会的地方：

• 多项式算法也可能有很大的常数或次数，实际并不好用；指数算法遇到小输入、好结构，也可能很快。
• 理论中的分类主要讨论最坏情况、精确回答、输入规模可不断增长，不是承诺每份数据都一样难。

所以，把“多项式时间”口语化成“快”很方便，但脑子里最好保留这几个限定。Barak 的计算理论教材对输入、验证和这些分类给出了正式定义。

三、P 和 NP：能直接判定，与能检查“有”的证据

P：有多项式时间算法，直接回答是或否

P 是能在确定性多项式时间内求解的判定问题集合。

比如：给定一个图，问两个点之间有没有路径。我们可以系统地搜索能到达的顶点，不必枚举所有可能路线，就能回答。

没有路径时，算法也必须结束，并正确回答“没有”。只在有解时找得到答案，不足以说明问题属于 P。

NP：如果回答是“有”，存在一份不太长、能快速核对的证书

NP 的要求不是“很难求解”，而是“是实例有多项式长度、可在多项式时间内验证的证书”。

输入有多长，证书就不能比它长得离谱；否则把宇宙那么长的证明交给你，一页页读完，已经失去了“容易检查”的意思。

硬币的选择编号是证书；旅行商的访问顺序也是证书。验证器接到证书后，要能快速判断它是否有效。

这里的“证书”有一个不对称性：

NP 保证的是“有解”时存在好检查的证据，不自动保证“无解”时也有同样好检查的证据。

一条符合预算的路线，可以证明“有”。交来十条不符合预算的路线，都不能证明“没有”。至于“无解证据”的一般理论，会涉及 coNP；这一篇先不把新缩写塞满桌子。

NP 的全称是 Nondeterministic Polynomial Time，非确定性多项式时间，不是“Non-Polynomial”，更不是“不能用多项式时间解决”。

为什么 P 一定包含在 NP 里面？

因为一个问题如果本来就能快速求解，验证时直接把问题算一遍就行，甚至不需要别人提供有帮助的额外证书。

因此，我们已经知道：

\[\mathrm{P}\subseteq\mathrm{NP}.\]

未知的是这个包含是否严格：NP 里是不是还藏着一些不属于 P 的问题？

把 NP 解释成“目前大多算不出来的问题”，会把已经确定属于 P 的那一大块直接漏掉，也会把“没有多项式通用算法”误读成“任何实例都做不了”。教材关于 NP 的定义及 P⊆NP 的论证正好可以检查这两点。

四、归约：我不会做 A，但能把它交给解决 B 的机器

现在进入最容易把方向记反的一步。

假设我们会把问题 A 的任意输入，在多项式时间内翻译成问题 B 的输入，并且：

A 的原输入回答“是”，当且仅当 B 的新输入也回答“是”。

“否”也必须对应“否”，不能只会把有解的例子翻过去。

这种翻译叫多项式时间归约，记作：

\[A\leq_p B.\]

本文统一使用多项式时间多对一归约：一次转换，得到一个 B 实例，保留是／否答案。不把它与允许反复询问子程序的其他归约方式混用。

图 3：沿箭头从上往下读。闪过的描边只依次提示“转换→判定→返回”，不是运行耗时比较；所有步骤一直可读，播放一次后停留，减少动态效果时不播放。B 判定器是推理中假设可用的工具，并不表示它已被实现。单独打开，刷新可重播。

为什么这说明 B 至少和 A 一样难？

因为如果 B 有一个通用的多项式算法，我们就能先翻译，再调用它，顺便把 A 也在多项式时间内解决掉。转换后的输入不会大到失控，因为写出它本身也必须在多项式时间内完成。

一定记住这个方向：

要证明新问题 B 很难，把一个已知难的 A 归约到 B。

不是把 B 归约到 A。

“把我的新问题交给难题机器去做”，只说明它可以被那台机器处理，不说明它自己一定很难。

归约也不能偷偷把原题先解完，再输出一个“有”或“无”的固定样例。除非你本来就已经能在多项式时间内解原题，否则这相当于把困难藏进了翻译器。

Barak 教材的归约章节明确给出这个方向、等价条件，以及“多项式转换＋多项式求解仍是多项式”的理由。

五、真的翻译一次：从“绕点一圈”到旅行商预算

光说“翻译”仍然有点虚。我们做一个完整构造。

原题叫哈密顿回路问题：

给定一张无向图，能不能沿图中的边走一圈，每个顶点恰好访问一次，最后回到起点？

这本身是一个已知的 NP 完全问题；这里用它作起点，展示怎样把难度传给旅行商，不在这一篇展开它的 NP 完全性证明。

图里有 n 个顶点，至少三个。我们不猜路线，只按下面的规则改造输入：

1. 每个顶点变成一座城市。
2. 两个顶点原来有边，新距离就设为 1；原来没边，新距离设为 2。任意两座不同城市都有距离，距离对称。
3. 把预算设为 n，问有没有总长度不超过 n 的旅行商闭合路线。

图 4：每组先看左边的原图，再查右边矩阵：有边写 1，无边写 2，对角线写 0。下方给出新问题的一条最短路线。上下两组分别保留“是”和“否”；距离为人为构造的无量纲成本，不是图上直线长度，更不是实际地图。

先看“原图有环”这一边。如果原图有哈密顿回路，新问题沿它走一圈，每段成本都是 1。n 段，总成本正好 n，满足预算。

再反过来。如果新问题有一条成本不超过 n 的闭合路线，它恰好包含 n 段，每段又至少是 1，因此只能每段都是 1。成本为 1 的边都来自原图，于是它就是原图中的哈密顿回路。

两边都说通，才叫保留答案。

转换快不快？只需检查各对顶点是否有边，填出一个 n×n 矩阵，再写下预算。不必先找到回路，也不必先解旅行商；输入大小和转换时间都是多项式级别。

所以：

\[\text{哈密顿回路}\leq_p\text{旅行商判定问题}.\]

注意，这个证明不是“因为旅行商看起来难”，也不是只拿两张小图试验。小图帮助看懂，一般的两向论证才保证任意输入都成立。

顺便一提，这个 1／2 距离还满足三角不等式：直接走至多是 2，绕另一座城市至少是 1＋1。后面有近似保证的旅行商问题，正好也需要这种条件。

哈密顿回路、NP 完全性的证明框架与归约方向，可参看南卡罗来纳大学的算法课程讲义。图中的转换按上述规则原创绘制，并用枚举检查小规模实例；枚举检查不是一般证明的替代品。

六、NP-Hard 与 NPC：一个是难度要求，一个是两项条件同时满足

现在才适合打开这两个名字。

NP-Hard：NP 中的每一个问题，都能在多项式时间内归约到它。

它表达的是一种相对难度关系：假如你真能在多项式时间内精确解决这个问题，那么所有 NP 判定问题也都能在多项式时间内解决，于是 P＝NP。

这里说的“所有”，是我们定义的 NP 判定问题，不是宇宙间一切问题。

NP-Complete，简称 NPC：既属于 NP，又是 NP-Hard。

两份资格都要有：

• 先说明“有”的证书长度合适，检查足够快，即它属于 NP。
• 再证明所有 NP 问题都能归约到它，即它是 NP-Hard。

因此：

\[\mathrm{NPC}=\mathrm{NP}\cap\mathrm{NP\text{-}Hard}.\]

NPC 可以理解成 NP 中最难的一批代表问题，但“最难”指多项式归约意义，不代表每个小实例都难，也不代表运行时间常数或实际算法表现完全一样。

为什么攻克一个 NPC，就会牵动整片 NP？

以旅行商判定问题为例。检查一条给定路线是不是符合要求，可以在多项式时间内完成，所以它属于 NP。上一节又把一个已知 NPC 归约给了它；归约具有传递性，所有 NP 问题便都能绕道归约过来。因此它也是 NPC。

如果它有多项式算法，NP 里的每个问题都能通过翻译享用这个算法。结合已经知道的 P⊆NP，得到 P＝NP。

反过来，如果 P＝NP，每个 NPC 自然也属于 P。

这叫“同一张归约网里的枢纽”，不叫“已经证明绝不可能快速求解”。

第一块枢纽从哪里来？

不是先凭直觉选一道看起来难的题，再宣布它代表全部 NP。

库克—列文定理把“多项式时间内能验证的计算”，编码成逻辑约束，证明布尔可满足性问题 SAT 是 NP 完全的。这是 NP 完全性理论的起点；然后人们通过归约，把枢纽连接到更多问题。

SAT 问：有没有一组真假赋值，让整个逻辑公式成立？给出赋值后，逐条代入检查很容易；定理真正深的部分，是为什么所有 NP 问题都能翻译进来。

Barak 教材的库克—列文定理章节从验证器讲到逻辑约束的编码，也解释了为什么一项 NP 完全性结果能够传递给其他问题。

七、关系图最容易画错的地方：我们还不知道两个圈会不会重合

图 5：先读顶部“假设 P≠NP”，再看交集标为 NPC。P 与 NPC 分离是该假设下的结论，不是已解决的事实；NP 内的留白不能一概叫 NPC。下方列出另一种可能。面积与距离不表示问题数量或难度大小，两种情景不能叠成同一张已知地图。

把核心关系整理成表，应该这样读：

类别	能否多项式时间精确判定？	“是”的短证书能否多项式时间验证？	关键关系
P	能	能，直接求解也行	P⊆NP
NP	其中 P 部分能；是否全部能，未知	能，这是定义	不能把 NP 当成“难题”的同义词
NPC	尚无已知多项式算法；任一个有，就有 P＝NP	能	NP 与 NP-Hard 的交集
NP-Hard	若有多项式算法，则 P＝NP；不保证反过来	不保证	不要求属于 NP，甚至不要求可判定

最后一行为什么写“不保证反过来”？

因为 NP-Hard 不只是“比 NPC 再难一点”。它可以跨出 NP，包含不可判定问题；即使 P＝NP，也不会让不可判定问题突然有了算法。

以一般停机问题为例：给定程序和输入，问它最终会不会停止。我们可以把 SAT 的公式写进一段程序：枚举真假赋值，发现满足公式的赋值就停止；所有赋值都不满足时，就进入无限循环。

这段程序会停，当且仅当公式可满足。生成程序的工作只是把公式嵌入固定代码模板，可以在多项式时间内完成，不需要先跑完枚举。这给出 SAT 到停机问题的多项式归约；结合 SAT 的 NP 完全性，停机问题就是 NP-Hard。

但停机问题不可判定，所以不属于 NP——NP 问题毕竟可以枚举有限长度的全部候选证书，最终作出判定，只是未必快。停机问题的不可判定性见计算理论教材。

说它“连别人给你答案都不能验证”也太笼统：一份真实的有限运行记录，可以说明某程序确实停止了；问题是一般停机没有 NP 所要求的、长度统一受输入多项式限制的验证机制，更没有对所有输入都结束并正确回答的判定算法。

八、旅行商、背包和 SAT：名字相同，问法可能差很多

现在回头看日常语言里的“解决这个问题”，就要小心了。

问法	要做的事	本文讨论的地位
有没有总长不超过 X 的旅行商闭合路线？	判定	NPC
找一条全局最短的旅行商闭合路线	优化并输出路线	NP-Hard；不直接把求最优值的任务放进判定类 NP
给出的路线是不是合法、总长不超过 X？	检查这份证书	多项式时间可做
给出的路线是不是全局最短？	排除所有更短路线	不能只靠加总长度来验证
这些物品能否在重量不超过 W 时，价值至少达到 V？	0／1 背包判定版，整数按二进制编码	NPC

“NP 是答案好检查”，通常指第三行那样的可行证书，不是自动包含第四行的最优性证明。

找最优路线的任务为什么 NP-Hard？因为如果你会快速精确优化，就能拿最优值与任意预算 X 比较，顺带回答判定题。这是借助优化算法解决判定问题；不把输出最优路线的函数任务与前面定义的多对一判定归约混为一谈。

判定器有时也能帮助找答案。对 SAT，如果已经知道有解，就逐次尝试固定一个变量，再问剩下的约束还有没有解；每次保留仍可满足的选择，至多按变量数再查询一轮，就能构造出赋值。但这是一串判定查询来做搜索，不是“交一条路线等于证明它最优”。

背包不是有动态规划吗？怎么还会是 NPC？

这正好检查我们有没有认真量输入长度。

常见 0／1 背包动态规划，按物品数 m 和整数容量 W 填表，表格量级为 mW。它在容量不大时很好用。

但 W 这个数值的大小，不等于写下 W 需要的位数。

容量从 1024 变到 1,048,576，二进制表示只从 11 位变到 21 位，表格宽度却放大 1024 倍。这叫伪多项式算法：对数值大小是多项式，不一定对二进制输入长度是多项式。

所以，“有动态规划”与“该一般判定问题是 NP 完全的”并不矛盾。容量小的实例仍然可以很好做。康奈尔讲义专门解释了这个区别；这里没有把“动态规划”当作自动消除复杂性的口令。

九、工程师怎么办：不是逃过定理，而是改变要交付的承诺

假设你在做派单或排程，老板不会接受“复杂性理论还没解决，所以今天不送了”。

但先别急着给任何业务都贴上 NPC：真实派单可能还有多车、时间窗、容量与动态路况，不同模型复杂性不同。有些分配问题可以归到多项式可解的匹配或流模型；“看起来像排班”不是 NP-Hard 的证明。

确认模型后，常见路线有三类。

1. 仍然求精确解，但利用规模、结构与搜索

小规模时，穷举或动态规划未必不行；大规模时，分支定界、整数规划、SAT／约束求解器会利用约束、传播和剪枝，避免走遍所有组合。

它们可以在许多真实实例上表现很好，甚至证明最优；这不等于拥有覆盖所有输入的多项式最坏情况保证。

如果业务结构允许，还可以拆分区域、限制关键参数、固定部分决策。但分区、固定决策可能牺牲原问题的全局最优，不能把改过的问题的最优解，冒充原题的最优解。

2. 求近似解，并证明它“最多坏多少”

不是所有“差不多”都叫有保证的近似算法。

以度量旅行商问题为例：城市间距离对称、非负，并满足三角不等式——直接从 A 到 C，不比经 B 绕过去更贵。先找一棵把所有城市连起来的最小生成树，再沿树往返，最后跳过重复城市，就能得到一条有保证的路线。

图 6：先看树的三条边，3＋4＋3＝10；再沿文字顺序走，所有树边各走两次，总长 20；最后去掉重复访问，得到 A→B→D→C→A，长 16。四点按 3∶4 的矩形等比例绘制，任意两点距离都按欧氏距离算；两条对角线各长 5。路线交叉在此模型中不违法，交点也不是新增城市。

这张图没有碰巧画个好结果就宣布成功。它背后有适用于一般度量实例的理由：

第一步：树的成本不超过最优旅行商路线。从一条最优闭合路线删去一条边，就留下连接所有城市的生成树；最小生成树不会比它更贵。

第二步：沿树往返的成本，是树的两倍。每条边各走两次，就能访问全部城市并返回。

第三步：跳过重复城市，不增加成本。这一步依赖三角不等式，不是无条件“抄近路一定划算”。

把三步串起来：

\[\text{返回路线成本} \leq 2\,\text{最小生成树成本} \leq 2\,\mathrm{OPT}.\]

OPT 表示该实例的最优旅行商成本。这个方法叫 2-近似：在条件成立时，对任意输入都保证成本不超过最优的两倍，不是“平均大概两倍”。

图中返回 16，最优为外圈的 14，因此并非精确解；它也没有达到两倍的最坏界限。这个小例子用来帮助看清构造，一般保证来自上面的三步证明。MIT 的旅行商近似算法讲义给出了这一证明。

三角不等式若不成立，就不能照搬这个结论。近似比还会因问题、约束、目标而变，并非任意 NP-Hard 问题都有好用的常数近似。

3. 用启发式，在给定时间内寻找更好的可行解

比如先贪心找一条路线，再局部替换几条边；或者用模拟退火、禁忌搜索等方法尝试跳出局部最优。图中的交叉路线，做一次合适的两边交换，就能从 16 改成外圈的 14。

这个小例子成功，不代表“局部交换永远能得到最优”，更不是给所有启发式颁发近似比保证。

OR-Tools 的路由选项文档列有初始解策略、局部搜索、模拟退火、禁忌搜索及时间限制。这类工具能帮助按时间预算求解，但设置十秒截止，不等于十秒内一定有解，更不等于十秒内证明最优。

真正应该交付的，不只是一条路线

实际系统最好把以下信息分开：

要报告的东西	它实际承诺什么
已找到可行解	通过了全部建模约束；还没说最优
当前最好成本 U	目前找到的最小成本，是最优值的上界
已证明下界 L	最优值不会低于它；需要求解器或数学论证支持
证明最优／证明无解	搜索与界限已足以证明，不等于“时间到了”
超时且未找到解	尚不知道，不等于不存在解

例如，一个最小化问题有合法成本 108，又有可靠下界 100，就能说最优值在 100 与 108 之间。这还给出相对于下界的 8% 差距，并保证当前解相对最优值的超额比例不超过 8%；前提是下界为正且确实有效，不能凭经验猜一个。

近似算法靠定理交代误差，启发式靠策略寻找好解，精确求解器还可能靠界限证明质量。三者不是三个“瞎凑一下”的名字。

十、把四个词收回一句话

如果只记一个问题，就记这个：

能快速检查一份“有”的证书，是不是意味着也能快速判断这份证书是否存在？

P 说“能快速判定”；NP 说“是实例有可快速检查的短证书”。

NP-Hard 说“所有 NP 问题都能快速翻译给我”；NPC 再加一条“我自己也在 NP 里”。

归约告诉我们，许多表面完全不同的问题，其实连在同一张计算能力的网上。工程实践则提醒我们：先问清楚要可行、要最优、要多好的近似、还是要在几秒内给出有质量说明的方案，再谈选什么算法。

计算机不是不够努力。真正有意思的，是我们还不知道：有没有一种更聪明的办法，能把这一整张网一起松开。

参考资料与图解说明

本文中的硬币、四点归约与矩形路线均为原创教学构造，不是实测业务数据。配图及其生成脚本保留在仓库中；候选数、证书求和、小规模归约、最小生成树与路线长度均由程序核对。数值检查辅助发现错误，不代替文中的一般性证明。

• 问题是否解决：克雷数学研究所：P vs NP。支持 P／NP 问题的直观表述与未解状态。
• 定义、短证书、P⊆NP、NP 完全性与两种可能：Boaz Barak《Introduction to Theoretical Computer Science》：NP 与库克—列文定理。也支持不能将 NP 理解成“非多项式”，以及不能把 NP 中 P 以外的区域全部当成 NPC。
• 归约的精确定义与方向：同书：多项式时间归约。支持多对一转换、保留是／否答案、多项式时间组合与归约传递性。
• NP 完全性证明怎么分两步：南卡罗来纳大学 CSCE750 算法课程讲义。支持哈密顿回路的题目定义、证书验证、NP-Hard 的归约方向及 SAT 的 NP 完全性。
• 子集和、背包与输入编码：康奈尔大学 CS4820：Subset Sum is NP-complete。支持子集和的 NP 完全性、它作为背包特例的关系，以及 mW 动态规划为何是伪多项式。
• 不可判定性不是“慢一点”：Barak 教材：Universality and uncomputability。支持一般停机问题不可判定。正文另外写明 SAT 到停机问题的程序构造，避免仅凭“很难”就认定 NP-Hard。
• 有条件的近似保证：MIT 6.046J：旅行商近似算法。支持度量条件、最小生成树下界、往返与跳点的 2-近似证明。本文区分优化任务与判定类，不沿用部分讲义中把两者简称为同一个 TSP 的宽泛措辞。
• 工程搜索的能力与状态：Google OR-Tools：Routing Options。支持启发式、搜索时限，以及“未找到”“超时”“已证无解”等状态不能混同；不将某个策略名称当作自动附带理论近似保证。