【漫士】这可能是人类提出最深刻的数学/计算机问题

以扫雷为例引出P是否等于NP：它是七个千禧年大奖难题中表述最短的一个，却可能是人类提出过的最深刻的数学问题。若能找到又快又通用的办法判断任何扫雷局面中所有没有雷的方块，或反过来证明这样的方法不存在，都能拿到100万美元。

同样的100万美金还藏在数独、俄罗斯方块、快递车路线甚至蛋白质折叠的方式里。若P等于NP，今天保护网上银行和聊天记录的加密算法原则上都能被攻破，数学家的大部分工作也可以交给机器；若不等于，则说明宇宙里有些问题找到答案就是比检查答案困难得多。

UP主自述本科专业是理论计算机，是姚班毕业生，一直想做一期视频好好讲P和NP问题，并称这将是最系统、最深入浅出、最专业也最有趣的科普。

以十个数为例比较四个任务：求和依次相加九次得总和508，找最小值打擂台比九次得16，朴素排序共比45次，而等和划分要挑出和为254的一组，只能穷举二的十次方即1024种分法，答案是十九、二十二、五十一、七十八、八十四，且分法唯一。

随数字个数N增大，求和与找最小约需N步，朴素排序约需二分之N的平方步，等和划分却要二的N次方种分组，每多一个数工作量翻一倍。每秒十亿次的电脑算30个数只需一秒，60个数要36年，100个数超过地球年龄，200个数算到宇宙终结也无解。

硬件提速追不上指数增长：速度提高1000倍，排序能多处理30倍数据，二的N次方算法却只能多处理十个数。1971年最快计算机每秒3000多万次，今天快约600亿倍，等和划分却只从一秒处理25个数变成60个，多35个而已。

分析算法步数很麻烦，运气好坏差别巨大，因此复杂度通常取最坏情况，即所有长度为N的输入中步数最多的那一个，它给出一个保证：经过这么多步一定有结果。但最坏情况的精确表达式往往复杂甚至无法写出，理论便忽略次要矛盾，只看增长快慢。

渐进复杂度分析比较函数增长：3N平方log N与N三次方减N相比，后者在N很大时步数更多，因为两者比值趋近于零。大O记号指从某位置起tn不超过C乘N的平方，系数与低次项被常数吸收。求和与找最小是O(N)，朴素排序是O(N平方)，都属多项式增长；二的N次方迟早超过任何C乘N的K次方，是指数增长。

复杂度分析历史悠久：公元前300年前后欧几里得《几何原本》记载辗转相除法，1844年拉梅证明其除法次数不超过较小数位数的五倍，被视为复杂度分析的开端。1965年杰克埃德蒙兹在图上匹配论文的题外话中提出，按多项式增长的算法是好算法，科巴姆、哈特、马尼斯和斯特恩斯也在同期论文中给计算难度分级，复杂度理论由此诞生。

能在多项式步数内解决的问题归为P类，取自polynomial，求和、找最小、排序都属于P。面对N的1万次方与1.0001的N次方之辩，回答是实用主义的：现实中多项式算法次数至多N的六次方左右，指数算法基本是二的N次方。更深刻的原因在于高效算法只做有限次加法乘法，多项式嵌套仍是多项式，体现一种闭包。

等和划分是否属于P仍无答案：目前想不出比遍历所有子集更好的方法，那是指数级复杂度。但想不出好办法不等于不存在，也许有聪明精妙的多项式方法只是人类没想到，这样的事并非没有发生过，不能总相信科学家叫苦叫难，例如排序就曾被认为困难。

介绍归并排序：把数字分成两堆递归排序，再逐层合并，每层N步、共log N层，总步数N log N，由冯诺依曼提出。相比选择排序最坏O(N平方)，家用电脑一秒十亿次运算下，选择排序只能排几万个数字，归并排序能排几千万个，体现算法优化的威力。

以2X加3Y在不等式约束下求最大值为例：每个不等式划掉半个平面，相交得凸多边形可行域，最优解在最后碰到的顶点，最大值为13。1947年Dantzig提出单纯形法，从顶点沿棱爬到更优相邻顶点。但1972年Klee和Minty构造难题，使其最坏情况走遍二的N次方个顶点，复杂度指数级。

线性规划是否有多项式算法一度成为悬案。1979年苏联数学家哈奇扬提出椭球法：用大椭圆包住可行域，检查中心是否满足所有不等式，不满足则切掉一半，再用更小椭圆包住剩余部分，每次面积缩到约77%。可行域非空时面积有由输入位数决定的下限，故多项式步数内即可找到可行点或判定无解。该结果登上纽约时报头版，说明被怀疑无高效算法的问题其实有多项式解法。

质数判定长期只有概率性算法，试除法要试到根号X，而根号X随位数N指数增长。2002年阿格拉瓦尔等人发表论文PRIMES is in P，证明质数判定属于P。乘法方面，竖式需N平方次乘法，可加速到N的1.58次方，用快速傅里叶变换可达N log N。可见判断问题是否真的难，人类感觉靠不住。

1874年杰文斯在《科学原理》中问哪两个数相乘等于8616460799，指出从乘积找回质因数只能逐个试除，熟练计算员要花好几周，而相乘只需几分钟。1903年Cole分解出89681×96079，验证只需一次乘法，试除却要碰到第8687个质数。

1977年麻省理工三位研究者利用这种不对称性设计RSA加密：两个大质数的乘积公开用于加密，质数留在手里才能解密。实际网络中的RSA整数有617位，人类公开分解过的最大整数只有270位，2020年9月动用上千块显卡约30个显卡年，而计算两个100多位数的乘积手机一秒不到。

正确答案难找但验证容易的问题随处可见，像不知道密码时只能暴力尝试，验证却只需拨到数字按下开关。数独填起来绞尽脑汁，检查只需扫每行每列每个九宫格；等和划分检查只需把两堆各加一遍；扫雷只需对着每个数字验证周围地雷数。这种检查答案的流程叫检查程序，刻画这类问题的概念就是NP。

图灵机有一条无限长纸带，每格写一个符号，读写头记着状态，照规则表查表执行，直到进入接受或拒绝状态。任何程序都可改写成图灵机。据此精确定义P：存在图灵机和多项式p，对任意长度n的输入最多走p(n)步就停下并给出正确是或否的答案。

普通图灵机同一状态读同一符号只有一条确定规则。非确定性图灵机可任选一条规则，只要存在选法走到接受状态就算接受。这种不确定性正是NP中N的意思，即nondeterministic。

用非确定性图灵机解等和划分：第一段从左到右扫过每个数字，非确定性地标0或1代表分到左堆或右堆，共做n次选择；第二段确定性求和比较是否相等。若确实能平分，1024种选法里至少一种走到接受。可想象有神奇海螺每次猜对或分身同时探索所有分支，两段各约n步，总步数不超过2n，故等和划分属于NP。

有简单检查程序与被非确定性图灵机在多项式时间内接受是一码事，只需在检查程序前加一段非确定性开挂来猜答案。NP也可表述为：答案为是时存在一份能在多项式步数内确认答案正确的凭据。P里的问题都在NP里，因为确定性机器可看作拥有猜答案能力却从不使用，所以P是NP的子集，问题在于两个圈是否同一个圈。

1956年3月20日哥德尔从普林斯顿写信给冯诺依曼，此时冯诺依曼已确诊癌症坐轮椅，几周后住进Walter Reed医院。信中哥德尔先问候病情，再提出数学问题。此前人类已两次撞上数学边界：1931年哥德尔证明有些真命题无法在系统内证明，1936年图灵证明有些问题没有算法能解决。

哥德尔在信中问：判断命题有无长度为n的证明最少需多少步，记作f(n)。他认为f(n)增长慢完全有可能，那样思考可交给机器。这正是P与NP问题：检查证明快，寻找证明却要在天文数字般的写法里搜寻。

用考试及格的比喻说明规约：若有一种能力保证任何卷子都及格，就能把黎曼猜想等难题塞进卷子，从而被迫解决它们。这种利用系统能力撬动不可思议结果的过程叫规约，它能证明两个看似无关的问题存在联系，并说明一个问题不会比另一个更容易。

把数独的81个格子画成81个点，同行、同列、同九宫格的格子之间连线，每个点连20条线，再把1到9看成九种颜色，填数独就等价于九色染色。为固定题面数字，另加九个两两相连的调色盘点，把给定格子与除该数字外的八色相连，迫使其只能涂成对应颜色。于是图能染好当且仅当数独有解，能快速染色就能快速解数独。

给出规约的定义：把问题A的任何一道题在多项式步数内翻译成问题B的一道题，并保持答案不变，A有解当且仅当B有解，就叫把A归约到B。A能规约到B说明B的难度大于等于A，因此染色至少和数独一样难，绝不会比数独更容易。

科学家追问NP家族是否存在一个问题，所有NP问题都能归结到它。若有，它的难度大于等于所有NP问题，它有多项式算法则P等于NP，否则P不等于NP。这样的问题叫NP完全问题。

1971年库克发表论文，证明可满足性问题SAT是所有NP问题都能规约过去的问题。他从非确定性图灵机出发，把机器运行每一步的纸带内容、读写头位置与内部状态合称格局，为后续用表格编码运行过程做铺垫。

把第零步到第P(n)步的格局逐行排成表格，行数与列数都是多项式的。表格合法只需检查相邻两行中两行三列的小窗口是否符合规则表，每个窗口内满足某条规则是或的关系，所有窗口同时满足是且的关系，于是整张表能否合理填入零和一，就变成一个巨大的SAT表达式。

库克进一步证明这些要求可改写成每个从句最多涉及三个变量的3SAT。用四个开关和四盏灯比喻：每盏灯挂一条至少一项成立的要求，问怎样拨动开关让所有灯全亮；也可比作咖啡馆按顾客对三个变量的要求设计各种因素，让所有顾客都满意。SAT本身属于NP，给定拨法逐条检查即可，因此它是第一个NP完全问题。

几乎同时在莫斯科，Kolmogorov的学生Leonid Levin独立得到同样结论，其博士论文获导师与答辩委员会认可，苏联研究者把这类问题叫做perebor，意为穷举挨个去试。Levin的通用穷举问题1973年才发表，正文只有两页，他推迟发表是想把最小电路问题也放进去。今天该定理被称作Cook-Levin定理。

1972年3月，卡普在纽约州IBM研究中心研讨会上报告了21个NP完全问题，包括哈密顿回路、团与独立集、任务调度罚款、背包恰好装满、斯坦纳树总长限制等。它们与SAT地位相同：高效解决其中任何一个，就能在多项式时间内解决所有NP问题。

染色问题为何NP完全，原理仍是规约：已有3SAT这个最难问题，只需把任何3SAT翻译成节点数不超过变量数与从句数多项式的染色图，使图可三染色精确等价于布尔表达式取值为真。规约规模必须保持多项式，嵌套后最终问题规模才是原问题的多项式。

只用三种颜色，先用三角形构建染色盘，命名为T、F、B。每个变量xi构造xi与not xi两节点，与B连成三角形，迫使一真一假，相当于赋值。每个从句引入五个辅助节点，若三个变量全假则推出矛盾，从而迫使从句至少一个为真；整图可三染色即得3SAT的解。

卡普注意到SAT可一路翻译成21个不同问题，证明它们都是NP完全的；1979年教科书附录已收录约300个NP完全问题，今天已有好几千个，遍布流程统筹、芯片设计、生物经济乃至投票机制设计。50多年来无人找到快速算法，因为它们是同一个问题；其共同核心是众多局部规则环环相扣、纠缠耦合甚至互相矛盾，需整体协调，因而极为棘手。

2000年伯明翰大学数学家Richard Kaye发表论文证明扫雷是NP完全的，同年Ian Stewart在Scientific American撰文称百万美元扫雷。证明思路是把任何3SAT清单翻译成扫雷局面，原式可满足当且仅当该局面存在自洽埋雷方式。

从扫雷最后两格生死二选一的名场面出发，把二选一当作零和一的开关：X有雷为高电平，X撇有雷为低电平。按XX撇一重复排列，上下两行的一保证每对恰好一颗雷，夹在中间的一使相邻两对联动，整根导线的叠加态被串在一起，导线还能拐弯、分叉与交叉。

Kaye为逻辑电路设计整套逻辑门，用扫雷数字结构实现取反得到NOT，再组合出AND与OR。于是任何3SAT布尔表达式都能编译成扫雷局面：每个变量是一根输入线，每条从句经两次或门接入变量或其取反，所有从句用与门连接，最终输出接入必须为真的终端。

扫雷不比SAT容易，至少和所有NP问题一样难；核对埋雷是多项式的，故扫雷是NP完全问题。

NP完全不意味着人类束手无策只能暴力枚举。NP完全说的是最坏情况，现实题目多有结构：2025年人们算出韩国8万多家酒吧间的最短巡回路线并证明最短，芯片公司每天用SAT求解器处理上百万变量的清单。放松全部满足的要求后，随机方法期望满足7/8从句，超过这一比例则NP等于P。

斯科特阿伦森写道，如果P等于NP，能欣赏交响乐的人都会立刻成为莫扎特，能跟上论证的人都会成为高斯。老手与新手不再有区别，经验、直觉和品位本是能在指数多可能性中更快找到对的路，若找到和验证一样容易，这些就不再值钱。

如果P等于NP，密码学也会随之消失。网上几乎所有加密都建立在正着算容易、倒着推很难的基础上，比如两个质数相乘容易而分解困难，椭圆曲线密码同理，2024年定下的抗量子标准也不例外。若任何快速正算都能被快速倒推，这些密码就全都不靠谱。

加萨奇三次调查显示认为P不等于NP的人从2002年的61%涨到2012年的83%，再到2019年的88%；高德纳则渐渐相信P等于NP，只是多项式次数可能大得无法想象。沃金格维护的网页收录116份宣称解决该问题的论文，61份说等于、49份说不等于，没有一份站得住脚。

以尺规作图不可能问题作类比：证明一类方法做不到某事，需先本质概括该类方法并找出能力边界。但P≠NP有悖论式困难，因为人类能想到的算法都在P内，却要证明无穷多未曾想到的算法都无法高效解决某问题，如同只会数数却要证明ZFC无法证明黎曼猜想。

人类用逻辑电路建模多项式算法，算法步数对应门数大致为平方。证明某NP问题所需门数超过任何多项式，即可证明P≠NP。香农1949年论证绝大多数布尔函数需指数级门数，但至今具体函数最好下界仅约3.1N个门。

指数时间假设比P≠NP更具体：不仅认为NP完全问题没有多项式算法，还给出至少指数级时间的下界，3SAT与等和划分都逃不开某个C的N次方；更强的SETH假定指数必须是二的N次方。科学家几乎都相信它，因为密码锁各密码无联系时最坏情况只能逐一尝试。

2024年10月26日OpenAI公开手稿，声称找到确定性算法，可在二的根号log N分之N次方时间内精确数出3SAT的解数，量级上快于任何C的N次方。证明尚未经同行审查。若成立，几百篇以其为前提的论文结论都要推倒重来。

流传的说法称肥皂膜会收缩到面积最小状态，粘在钉子间就能找出连接钉子的最短网络，即NP难的斯坦纳树问题。2005年阿伦森做实验，用玻璃板夹铜钉浸肥皂水：三四根钉子时通常能找到最短网络，但钉子一多常停在更长的形状和局部极小值上，还会出现最短网络中不可能有的三条膜围成的小三角形，重复实验形状也不同。

阿伦森在2013年出版的书中提出，也许应把NP完全问题在物理世界没有高效解法当作一条物理原理，如同热力学第二定律：永动机造不出来，它没有被证明。至今电脑、肥皂膜和量子计算机都没打破这个规则。若规律成立，我们身处找答案比验证答案难得多的宇宙，正因如此秘密才守得住，好想法才珍贵。

若NP真的等于P且算法非常高效，世界将无比令人兴奋但也恐怖至极。UP主总结这是NP与P问题的科普，并说明自己本科是理论计算机方向的姚班毕业生，本期倾注大量心血，希望观众点赞支持并关注，预告将做更多科普。