P 与 NP 问题——悬赏 100 万美元的计算难题

大家好，我是 Senko。本文将解读计算机科学最大的未解决问题“P 与 NP 问题”。

解数独很费劲，但要给声称解出来的人验算，只要一瞬。拼拼图很辛苦，可与完成图一对照，一眼就知道。把这份日常感受推到底，就会撞上一个了不得的问题：“能一瞬间验算完的问题，会不会其实也能一瞬间解出来？”你大概会觉得“怎么可能”。可是，“这个‘怎么可能’谁也没能证明”。这就是 P 与 NP 问题，解决它可获得100 万美元奖金。

“解开”与“确认”是两份不同的活

P 与 NP 问题的主角，是“给问题的‘难度’做度量”这个想法。在计算机科学里，难度是用“当问题规模变大时，计算时间怎样增长”来衡量的。

P 是这样一类问题的集合：规模变大时，计算时间也只以现实可接受的节奏增长。乘法、排序、地图上找最短路径。这些即便规模变成 10 倍，时间也只是缓慢增加，被称作“能高效解决的问题”。

NP 则是“只要给出一个候选答案，就能高效确认它是否正确”的问题集合。数独是典型：格子一多，解起来会急剧吃力，可对填好的盘面做验算，很快就完事。

这里要紧的是，能高效解开的问题，必定也能高效确认（既然解出来了，当然能确认）。所以 P 包含在 NP 之中。问题出在反方向：“确认得快的问题，是不是解起来也都快？”换句话说，P 与 NP 是同一个东西，还是真的两码事——这就是 P 与 NP 问题的全文。

1971 年，人们发现问题里有个“王”

把这个问题搬上数学擂台的，是 1971 年斯蒂芬·库克的论文（苏联的列昂尼德·莱文也独立作出了同样的发现）。库克证明的是一个惊人的事实。

在属于 NP 的问题当中，存在“只要这个问题能被高效解决，NP 的所有问题就都能被高效解决”的万能问题。这类问题被称作“NP 完全”。最早被证明为 NP 完全的，是“逻辑式的可满足性问题”。

次年 1972 年，理查德·卡普又指出现实社会中 21 个有名问题清一色都是 NP 完全。此后名单不断增加，如今已知有数千个问题属于 NP 完全。举几个例子。

“旅行商问题”：走遍众多城市的最短路线是哪条
“背包问题”：在容量限制内价值最大的物品组合是哪个
“排课表”：满足全部约束的课程安排是否存在
“数独（一般化版）”：n×n 的数独有没有解

NP 完全问题是彼此可以互相翻译的命运共同体。只要其中任何一个被找到高效解法，全体就会一齐失守、P=NP 就此确定；反之只要其中任何一个被证明“无法高效解决”，全体就一齐确定不破，P≠NP 也就定了。数千个问题手拉着手，一起站在悬崖边上。这个构图之漂亮，让 P 与 NP 问题成了一个特别的存在。

为免误解补充一句：NP 完全并不等于“现实中束手无策”。求解最早那个 NP 完全问题（逻辑式可满足性）的程序“SAT 求解器”，与最坏情况的理论相反，日常就在求解数百万变量规模的实例，在半导体设计验证与软件测试中实际发挥着作用。理论最坏与实务典型为何差得这么远，其实也没弄清楚。大谜团脚下堆着小谜团，正是这个领域的样子。

若 P=NP，世界会变成什么样

很多未解决问题即便解开，日常也不会改变。P 与 NP 问题不同，它被说成答案不同，文明的景色就会不同，是个直连实利的问题。

假如 P=NP 被证明（且带来可实用的解法），首先互联网的公钥密码会崩塌。当前的密码把安全性建立在“验算容易、破解事实上不可能的计算”上，而在 P=NP 的世界里，那个“事实上不可能”会消失。

另一方面，好处也大得离谱。物流的最优路线、制药中的蛋白质设计、工厂的排程，这些 NP 完全的实务问题会齐刷刷变得可高效求解。更奇妙的是，由于“确认一个定理的证明可以机械地完成”，于是拥有简短证明的数学定理就能被机器高效发现，甚至有人讨论数学家的一部分创造性会不会被计算取代。

那么专家倾向哪一边？针对研究者的问卷调查显示，八成以上预测 P≠NP。也就是说：“确认得快，未必解得快；世上存在本质上困难的问题。”这既合乎日常感受，也有一条经验之谈——若真是 P=NP，早该有人找到那个魔法解法了。可证明仍然没有。就“人人都信为常识的东西却没有证明”这一点而言，它与黎曼猜想并列双璧。

阻挡证明的那些“墙的证明”

P 与 NP 问题有意思的地方在于，“为什么证不出来”本身也被研究，并成了定理。

在尝试证明的热潮之后，研究者们注意到一个古怪的事实：那些看着有希望的证明技法有着共同的类型，而属于该类型的技法在原理上无法解决 P 与 NP 问题——这一点被分别证明成了定理。“相对化之墙”“自然证明之墙”等等，这些结果就像是“这座山靠这套装备爬不上去”的禁止登山告示牌。

也就是说，现状不只是山高，而是已知的多数路线上都立着此路不通的证明。人们认为，要解决它，需要一种不属于任何既有类型的、全新的数学。在克雷数学研究所的七个千禧年大奖难题中，P 与 NP 问题也常被评为“离解决最远”的一个。

我觉得这种“不可能性的证明越堆越多”的展开，是这个门类里最像科幻的风景。人类不只是解不开问题，而且“‘用这个方法解不开’这件事，倒是能证明出来”。数学那种自我指涉的强悍与瘆人，都浓缩在这里了。

量子计算机能解决它吗

用超级计算机或量子计算机解决不了吗

解决不了。P 与 NP 问题是“是否存在快的步骤（算法）”而非“是否存在快的机器”的数学问题，机器进步是分不出胜负的。至于量子计算机，已知它能加速素因数分解等一部分问题，但素因数分解并不被认为是 NP 完全，人们也不预期量子计算机能高效解决 NP 完全问题。看到“量子解决 P 与 NP”这类标题，需要留个心眼。

实务中是怎么对付 NP 完全问题的

放弃正面求最优解，改成好好相处。具体有三根支柱：“用不最优但足够好的解将就的近似算法”、在实用输入上跑得飞快的启发式方法，以及规模小时硬算的求解器。导航、物流、工厂，全都靠这套将就的技术在转。NP 完全不等于“绝对解不开”，它的意思是“最坏情况下若要严格最优就吃不消”。这一点搞混，实务上的对话就会驴唇不对马嘴。

100 万美元要怎么才能拿到

证明 P=NP 或 P≠NP 哪一边都算。按克雷数学研究所千禧年大奖难题的规定，条件是刊登于专业期刊，并经受数学界两年的检验。几乎每年都有声称“我证明了”的论文发表、又在专家检验下崩掉，甚至有专门汇总这些结局的记录网站。挑战是自由的，不过先从享受一本讲 NP 完全概念的教科书开始，看着绕远，我觉得反而是最近的路。