观观市 登录
← 返回视频简报
漫士沉思录 已完成

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

2026-10-31 03:53 · 时长 70分23秒 · 模型 gpt-6.1-sol · 在 B 站打开 ↗
#计算复杂度 #算法理论 #数学难题

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

视频围绕 P 是否等于 NP，从算法效率、快速验证与快速求解的区别，讲到 NP 完全性、归约、证明难点及其对密码学和现实世界的意义。

  • 算法的增长速度，比计算机快多少更关键。 对 (n) 个数求和、找最小值需要 (O(n)) 次操作，选择排序需要 (O(n^2))，逐一枚举等和划分方案则有 (2^n) 种可能。硬件提速 1000 倍，平方复杂度算法可处理约 31.6 倍的数据，(2^n) 的枚举算法却只能多处理约 10 个元素。这说明指数增长会迅速抵消硬件进步。

  • 复杂度衡量输入增大后，算法所需资源如何增长。 视频主要讨论最坏情况下的时间复杂度；大 (O) 记号表示渐进上界，忽略常数与低阶项，例如 (3n^2+5n+7=O(n^2))。这里的输入规模严格说是输入的编码长度，包括数字的位数；多项式时间是理论上的效率标准，并不保证实际运行一定快。

  • P 是可以在多项式时间内求解的判定问题集合。 严格定义要求确定性图灵机对任意输入，都能在输入长度的某个固定多项式时间内，给出正确的“是／否”答案。求和、排序等计算任务是视频用来解释高效计算的直观例子，其相应判定版本可纳入这一框架。

  • 没有找到高效算法，不代表高效算法不存在。 归并排序通过“分成两半、分别排序、线性合并”，将排序复杂度从 (O(n^2)) 降至 (O(n\log n))。线性规划虽然有最坏情况为指数时间的单纯形法，却存在多项式时间的椭球法；2002 年的 AKS 算法则证明了素数判定属于 P。类似地，等和划分也有优于直接穷举的算法，只是目前没有已知的通用多项式时间算法。

  • NP 的关键是“肯定答案有可快速检查的凭据”。 例如，给出一种等和划分方案，可以快速核对两堆总和；给出数独填法，可以快速检查行、列和宫的约束。准确地说，NP 要求：答案为“是”时，存在长度为输入规模多项式的凭据，能够在多项式时间内验证。

  • NP 不是“Not P”，而是 Non-deterministic Polynomial time。 它也可以定义为非确定性图灵机在多项式时间内接受的问题：只要存在一条合法计算分支能够接受，就算接受该输入。“神奇地猜中答案”或“同时探索所有分支”只是理解模型的比喻，并不是现有计算机具备的能力。

  • P 与 NP 的问题是：快速验证，是否意味着快速求解？ 已知 (P\subseteq NP)，未知二者是否相等。若 (P=NP)，所有 NP 问题都有多项式时间算法；若 (P\ne NP)，则至少存在一个能够快速验证肯定答案、却无法在最坏情况下快速求解的问题。证明后者必须排除所有可能的多项式算法，包括人类尚未想到的算法。

  • 多项式时间归约，让不同问题的难度可以比较。 若能在多项式时间内把问题 A 的任意实例转换成问题 B 的实例，并保持“有解当且仅当有解”，就记作 (A\leq_p B)。这意味着 B 至少和 A 一样难：只要 B 能快速求解，A 也能。视频以数独转图染色为例，用连边表达同行、同列、同宫不能填相同数字的约束，再用“调色盘”节点表达已知数字。

  • NP 完全问题，是能够代表整个 NP 家族的核心问题。 一个问题既属于 NP，又能承接所有 NP 问题的多项式时间归约，就称为 NP 完全。只要其中任意一个有多项式时间算法，就能证明 (P=NP)；只要证明其中任意一个不存在这样的算法，就能证明 (P\ne NP)。

  • Cook–Levin 定理证明，SAT 是 NP 完全问题。 SAT 询问：是否存在一种布尔变量赋值，使整个逻辑表达式为真？证明的核心是将任意 NP 问题的计算过程写成一张多项式大小的“运行历史表”，再把初始状态、合法转移和最终接受状态编码成逻辑约束。3SAT 将每个子句限制为至多三个文字，例如 (x_1\lor x_2\lor\neg x_4)，仍然是 NP 完全问题。

  • 大量看似无关的问题，可以通过归约连接起来。 图的三染色、等和划分、哈密顿回路、背包的相应判定版本等，都具有 NP 完全性。扫雷的经典结果针对的是“给定数字布局是否存在一种一致的埋雷方式”：通过构造导线、逻辑门和输出约束，可以把逻辑表达式翻译成扫雷局面。数独及其他游戏的复杂度结论也必须针对可扩展的棋盘和具体规则版本，不能直接套用于固定大小的一局游戏。

  • NP 完全不意味着每一个实例都难，也不意味着只能暴力枚举。 复杂度结论关注最坏情况；现实实例常带有几何结构、稀疏关系或其他可利用的特征，因此 SAT 求解器、剪枝和启发式方法可以解决规模很大的实际问题。对于每个子句包含三个不同变量的 MAX-3SAT，随机赋值可在期望上满足 (7/8=87.5\%) 的子句；对所有可满足实例保证超过 (7/8+\varepsilon) 的满足比例，则存在以 (P\ne NP) 为前提的近似困难性结果。

  • 如果 (P=NP)，影响取决于算法是否实际可用。 足够快且可实现的算法，将大幅改变优化、自动证明和依赖计算困难性的密码学。但“多项式时间”可能具有极高次数或巨大常数，因此理论上的相等不等于立即破解现实加密。反过来，(P\ne NP) 也不能单独保证 RSA 安全，因为整数分解并未被证明是 NP 完全问题。

  • 电路复杂度是一条重要研究路线，但现有证明能力仍很有限。 多项式时间算法可以展开成多项式规模的布尔电路，因此，若能证明某个 NP 问题需要超多项式规模的一般电路，就能推出 (P\ne NP)。计数论证说明绝大多数布尔函数需要指数规模电路，但为明确构造的函数证明足够强的一般电路下界，仍然极其困难。

  • ETH、SETH 比 (P\ne NP) 提出了更强的时间下界猜想。 ETH 通常断言：以变量数 (n) 衡量，3SAT 不存在 (2^{o(n)}) 时间算法；SETH 则大意断言，对任意固定 (\varepsilon>0)，总存在某个子句宽度 (k)，使 (k)-SAT 不能在 (O((2-\varepsilon)^n)) 时间内解决。文字稿声称“2026 年 10 月 26 日 OpenAI 发布推翻 ETH 的手稿”，但未提供可核查来源，且同时称其尚未经过同行审查，这部分不能作为已确立的数学突破引用。

  • 物理系统和量子计算，也没有已知的通用捷径。 肥皂膜可能停在局部极小值，不能保证找出全局最优网络；目前也没有已知量子算法能在多项式时间内解决所有 NP 完全问题。视频最后借此追问：寻找答案比检查答案困难，是否反映了计算乃至物理世界的一种根本限制？

▸ 原始转写文字稿（20279 字符）
赚100万美元最简单的方法是什么?我不知道但我知道最难的方法那就是解决一道数学题P是否等于NP它是七个千禧年大奖难题中表述最短的一个却可能是人类提出过的最深刻的数学问题没有质疑它的源头是人类最古老的一门智慧、算法和最年轻的工业革命发明、计算机在20世纪中也相遇这100万美元就藏在这一具扫雷里如果你能找到一个又快又通用的办法根据任何一个扫雷局面判断出所有没有雷的方块那么这笔奖金就归你而反过来如果你能证明这样的方法不存在这个奖金也归你同样的100万美金还藏在数逐、俄罗斯方块、快递车的路线、甚至是蛋白质折叠的方式里如果答案是P等于NP那么今天保护网上银行和聊天记录的加密算法原则上都能被攻破数学家的大部分工作也可以交给机器如果答案是不等于就说明我们的宇宙里有一条规律有些问题找到答案就是比检查答案要困难的多难道再快的计算机也追不上50多年过去了依然没有人能回答它为什么会这样呢到底什么是P和NP问题呢作为本科专业是理论计算机的摇班毕业生我一直想做一期视频好好讲讲P和NP问题那么它来了这将是你见过最系统、最深入浅出、最专业也最有趣的关于NP和P问题的科普没有之一点赞收藏数学启动注意看这里有十个数我们一共有四个任务把它们加起来找出最小的那一个从小到大排好序最后要把它们分成两堆让两堆的和相等求和是最简单的从第一个数开始依次往后加加上九次我们就能得到总和508找最小的数也不难让数字量量比较小的留下来再和下一个比像打擂台一样一共要比九次最后留在台上的十六就是最小只排序要多费一些功夫最朴素的办法就是每一轮都从剩下的数字里用打擂台找出最小的那个数放到前面第一轮要比九次第二轮要比八次以此类推一共要比45次就能排好序了而第四个任务就不太一样了总和是508一半是254我们要从十个数字里挑出一组让它们的和恰好等于254你可以暂停试一试答案是1922517884分到一对而剩下的分到另一对这样两边的和都是254而且这是唯一的分法找一个人类来做这道题多半都是凭感觉去凑结果不对就换另一个分组再去试电脑没有感觉所以它最直接的办法就是把所有的挑法挨个试一遍每个数字都有进左边这堆和右边那堆两种去向10个数字就有2的十次方也就是1024种组合这样也能找到答案那这四个任务的难度显然有差距它们差在哪呢我们来看看当数字的个数n变大时需要的步数是怎么增长的求和与找最小值大约需要n步朴素的排序大约需要2分之n的平方步而把n个数分成总和相等的两堆这个问题则要困难的多它在计算机科学里有一个正式的名字叫做等和划分问题是子集合问题subset sum的特例一个个去尝试要2的n次方种分组的方法把数字个数从100个变成101个求和只需要多做一步排序的步骤只多出2%左右但等和划分却不同原来的每一种分组方式都要分别考虑新来的这个数放进左堆还是右堆工作量整整翻了一倍每多一个数就会翻一倍这就是指数增长对于一个算法来说指数增长的速度是非常可怕的就比如说这个等和划分问题用今天一台每秒运算10亿次的电脑30个数只需要算1秒但60个数就要算上36年要算明白100个数存不存在划分方法需要的时间会超过地球的年龄即便换成今天世界上最快的超级计算机每秒能够运算200多亿亿次计算n等于100也需要将近2万年如果数字多到200个最强的超算算到宇宙终结也算不出答案来本质上尽管计算机一直在变快可面对算法层面上指数增长的恐怖趋势硬件计算速度的提升几乎可以忽略不计把电脑的运算速度提高1000倍同样的时间内排序算法能够处理超过30倍的数据量但2的n次方的等和划分算法却只能多处理10个数因为对于2的n次方来说函数值增长1000倍只能让自变量增加101971年设计上最快的计算机每秒最多运算3000多万次今天最快的每秒是200多亿亿次在50多年里快了大约600亿倍然而对于等分两堆这个问题来说只不过从1秒钟能处理25个数变成能处理60个数 多35个而已一个算法究竟需要运行多久随着数据规模的增加需要的时间会怎么变化因此成为了理论计算机科学最核心研究的问题计算复杂度分析要知道分析算法复杂度是一个很麻烦的事情因为面对各种不同的数据算法到底需要多少步才能找到答案是非常复杂的就比如说等和划分问题有的时候你运气好那么第一次尝试就成功了有的时候运气不好要一直试完所有的排列组合才发现根本不可能那我们就把2的n次方个所有的子计全都过了一遍因此当我们说一个算法要走多少步的时候指的通常是最坏的情况算法的复杂度取的是所有长度为n的输入里步数最多的那一个这样得到的数字就是一个保证经过这么多步保证一定有结果因为最坏情况下也就只有这么多步但是问题接踵而至这个最多的步数写成n的函数往往长得很复杂很哆嗦比如说像这个样子甚至在很多情况下我们根本无法得到一个精确解析的表达式找到算法的最坏情况非常困难和繁琐这是该怎么办呢于是计算复杂度理论从一开始就忽略次要矛盾只关注它增长的快满比如说假如有另外一个算法的复杂度是n的三次方减n我们想比较它和之前的那个算法哪个更好此时我们可以把x轴不断缩放再缩放你会发现当n特别大的时候明显第二个算法的步数是更多的这本质上是一个类似比值极限的数字第一个复杂度最主要的项是3n平方logn而第二个则是n的三次方这两个式子的比值趋近于0所以前者的步数更少速度更快以上这套思路就叫做渐进复杂度分析1970年代初John Hopcroft和Robert Turgeon将最坏情况下的渐进复杂度确立为分析算法效率和好坏的核心标准核心记号就是这个大O学过泰勒展开的小朋友肯定见过而它正是渐进复杂度分析的核心方法当我们说一个函数tn是on平方的意思就是说能找到一个常数c从某个位置开始往后tn就永远不超过c乘以n的平方好像被cn平方这条曲线从上方压制住了3n平方加5n加7就是这样在n大于等于7之后它就始终在4n平方的下面这种记号的好处就是牢牢抓住了整个算法最核心的步骤数细数和d次项都被这个常数c吸收掉了决定增长的只有次数最高的那一项用这种说法求和与找最小值算法在最坏情况下也只需要线性于n的次数所以说它的复杂度是on的而普速的每次找最小值的排序最坏情况下需要2分之n乘n-1步最高像是平方所以这个算法的复杂度是on的平方它们的共同点就是都能被n的某一个常数次方压住这叫做多项式增长与之形成鲜明对比的则是等和划分的2的n次方不管把常数c取得有多大把次数k取得有多高2的n次方迟早会冲到c乘n的k次方上面这叫指数增长指数的底数拿把支币1大一点点结果也是一样的它会碾压性的比多项式需要更多的部数关注一个算法需要的总部数在人类的数学研究中历史悠久公元前300年前后欧几里德的几何原本就记载了求两个数最大公约数的辗转相处法这个算法今天仍然是加密程序里的常用工具1844年法国数学家拉梅证明辗转相除需要做的除法次数总是不超过较小的那个数位数的5倍所以一个100位的数字也不过几百步而已这个结果常常被看作是算法复杂度分析的开端在没有计算机的年代人能够守算的规模很小多项式和指数的差别不过是算的久一点和算的更久一点然而当计算机把N推到了成千上万这个差别就变成了几秒钟与永远1965年在美国国家标准局工作的数学家杰克·艾德蒙兹在一篇讲图上匹配算法的论文里专门写了一节题外话讨论什么样的算法才算是好算法他的回答是难度随着问题的规模按代数时也就是今天所说的多项式增长的算法是好算法而那种显而易见的穷举难度是指数增长的同一年前后科巴姆哈特·马尼斯和斯特恩斯也在各自的论文里用同样的方式给计算的难度分析计算复杂度理论computational complexity由此诞生能在多项式部数内解决的问题被归成了一类叫做P取自Polynomial多项式刚才说过的求和、找最小值、排序都属于P它们通常被认为是比较简单的问题因为存在一个好的高效的多项式算法你可能会质疑了多项式一定就更快更好吗?如果一个多项式的N需要N的1万次方但另外一个指数算法只要1.0001的N次方部呢?那在很大的范围里后者不是反而快得多吗?对这个问题计算机科学家的回答是实用主义的现实中一般没有这么极端的例子绝大部分的算法问题多项式算法的次数至多是N的6次方左右而指数算法基本上都是2的N次方这样的量级在N很大的时候基本上就是多项式算法能算得动而指数算不动除此以外还有一个更深刻的原因一个高效算法的特点是它不需要像暴力破解密码锁那样对每个变量逐一尝试而是用有限层千套的循环精巧的中间变量和地规的分制流程来解决问题它们的共有特点是指做了有限次的加法和乘法而从数据规模N开始做有限次加法和乘法的结果总是一个N的多项式如果一个多项式算法流程A的每一步是另一个多项式算法B那么总的复杂度就是两者的千套把A里的每个N都换成B里的N的多项式而多项式的千套还是多项式从这个角度上来说多项式复杂度这个概念同时也在刻画着一种B包也就是任何两个高效算法的串行并行或者复合其整体流程依然被视为是一个高效的算法那么问题来了把一堆数字分成总和相等的两堆这个等和划分问题是否属于P呢?到目前为止我们确实还想不出比一个个尝试所有组合更好的方法这需要便利这个集合所有的子集是指数级别的复杂度可是想不出好办法不等于不存在有没有可能是我们太笨了呢?是否会有一个聪明精妙的多项式方法只不过人类这么多年都没有想到过呢?要知道这样的事不是没有发生过我们不能总是太相信人类科学家在那叫苦叫难好多前人声称困难的没有办法的问题最后经常发现有一个高效的算法就比如说刚才所说的排序其实就有比平方更快的做法我们可以每次把数字分成两堆让每一堆各自从小到大排好序那么此时最小值就只可能出现在这两列数字的最前面这两个最小值当中的较小值就是所有数字的最小值我们就可以把它拿出来放到结果数列的开头经过这样的操作之后剩余数字的最小值依然只可能在两列数字的最前面出现我们可以再找出其中的较小值继续接在结果数列的后面重复这样的一个过程n次之后我们就可以把所有的数字都由小到大排好序了这个合并的过程只需要n次操作但你可能会说这是耍赖啊这两堆数字还得刚开始内部排序这个时间又怎么算呢答案是你可以完全用相同的方法层层向下低规比如说一级代理负责一半数字的排序那么他就会将这一半的数字进一步分成两堆交给二级代理排序再用自己n的时间合并两个二级代理的结果那你可能会问二级代理又如何排序呢答案是再找三级代理排好序然后自己合并因为每次向下代理任务时数字的规模都会减半所以在log2n次之后就只剩下一个数了这一级代理什么都不用做直接返回同一级的所有代理每个人都会单独处理一小段的合并而同一级所有合并操作的部数加在一块刚好就等于数字的总数n所以一层层累加logn级代理所需要的操作部数每一级n部一共就只需要n乘以logn部就可以完成排序了这叫做规并排序由冯诺依曼提出我们前面说过普速的每次找最小值的选择排序在最坏情况下需要on平方的部数而规并排序却只需要on乘logn这带来了巨大的效率提升普通家用电脑一秒钟大约是十亿次运算那么用选择排序只能给几万个数字排序而用规并排序则可以在同样的时间内完成几千万个数字的排序这就是算法优化的威力类似的事情发生过不止一次高中数学里我们都学过线性规划比如说在这几个线性不等式的条件下求2x加3y的最大值每个一次不等式都在平面上滑掉一半那所有的半平面全部相交之后剩下一个突多边形的区域叫做可行域我们把直线2x加3y等于z往右上方平移它离开可行域之前碰到的最后一个顶点是23给出了最大值13工厂排产物资的调运航班的排班本质上都是这样的问题这就是线性规划只不过真实场景的变量有成千上万个此时可行域就会从平面的多边形变成高维空间里的一个突多面体该怎么解这种高维空间线性规划的最优解问题呢1947年美国数学家Denzig提出了单纯刑法从可行域的一个顶点出发沿着棱走到目标值更大的相邻领点一步一步爬到最优的那个它在实践中非常好用可是1972年Glee和Minty构造出一类特别刁钻的难题能够让单纯刑法把2的n次方的顶点挨个全走一遍也就是说单纯刑法在最坏的情况下需要指数的复杂度那线性规划是不是就不存在多项式的高效算法不在P里呢不一定虽然单纯刑法最坏情况下需要指数复杂度但其他算法却可能在多项式部署内解决问题关键就在于这样的算法是否存在呢这个问题一时成为了悬案1979年苏联数学家哈齐扬给出了答案他提出了妥球法不去在顶点之间一步步跳转而是先用一个很大的椭圆把可行域整个包住然后检查椭圆的中心是不是依然在这个多面体之中如果中心满足所有的不等式就找到了一个可行点如果某一条不等式不满足可行域就只可能落在过中心和这条不等式边界平行的那条直线的一侧于是就可以把整个椭圆切成两半只留下可行域所在的那一半再用一个更小的椭圆把这半个包住每做一次椭圆的面积都按固定的比例缩小平面上每次会缩到原来的77%左右如果可行域不是空的它的面积就不会小于一个由输入数字的位数所决定的下限所以要不了太多次我们就可以找到那个可行点或者判断出最优解不存在一次次收紧就能逼近最优解总部数是输入长度的多项式这意味着一个很多数学家都怀疑可能不存在高效算法的难题其实有一个精妙的多项式算法线性规划在人类的统筹、调度、规划里极其普遍和重要而现在这类问题有一个通用的高效多项式算法这个结果也因此上了纽约时报的头版历史上这样的情况发生过很多次很多此前被人类长期认为不可能有高效解法的问题最终发现存在一个天才的多项式算法证明之前的研究者纯属自己不够聪明比如说能不能只用N的多项式以内的部数判断一个N位数X是不是质数普通的方法是拿2、3、4一个个去释除一直是到根号X为止而X大约是10的N次方根号X也有10的二分之N次方会随着位数N指数的增加很长的一段时间里人们只有很快的概率性算法却一直没有一个确定的保证在N的多项式部数内判断一个N位数是不是质数的方法2002年8月印度理工学院坎普尔分校的阿格拉瓦尔和他两个刚刚本科毕业的学生卡亚尔、萨克塞纳发表了一篇论文标题简单粗暴Primes is in P证明了判断质数存在高效的多项式算法属于P再比如说计算两个N位数相乘列数式相乘一共要计算N平方次乘法如果不是专门学过你可能很难想象这个问题的复杂度可以加速到N的1.58次方甚至用快速复列变换能够做到N乘以LogN所以想要判断一个问题是不是真的很难不存在多项式的快速算法人类的感觉是靠不住的因为可能只是我们很笨没有想到好方法而已要判断等何划分问题在不在P里就必须证明所有可能的算法包括那些人类还没有任何想到的那些都无法在多项式部署内完成一个人如何能证明所有的无穷多个潜在的算法甚至是自己没有想到的算法都无法在多项式时间内解决问题呢虽然给出问题通用且高效的解法很困难但很多时候验证一个具体的解答是不是正确答案却很容易1874年英国经济学家、逻辑学家威廉·斯坦丁·杰文斯出版了一本讲科学方法的书叫做《科学原理》书中有一节问读者能不能说出哪两个数相乘等于8616460799他接着写道我想除了我自己恐怕不会有别人知道了在他看来这两个数都是很大的指数要从成绩找回它们只能拿指数一个接一个的去释除一个熟联的计算员恐怕要花上好几个星期而他把两个因数乘在一起只花了几分钟那个年代的computer不是机器指的是以计算为职业的人这节的标题叫做《归纳是一种逆运算》杰文斯用乘法和因数分解来做比较从原因推出结果很容易而要从结果倒推原因则很难1903年美国数学家莱默把它分解出来了89681乘以96079你可以拿计算器验算一下只需要一次乘法可是要从2开始一个一个试质数得试8687个才能碰到89681虽然今天的电脑做完这8000多次释除用不了1毫秒但这种不对称性并没有消失只需要把数字的位数弄得再大一点计算成绩依然比逐一尝试每个质因数要快速的多1977年麻省理工的三位研究者正式利用了这个特性设计了著名的RSA加密算法两个大质数的成绩公开出去谁都可以拿它加密而两个质数留在自己手里只有知道它们的人才能解密今天在实际网络中所使用的RSA成绩有617位而人类公开分解过的最大成绩只有270位时间就在2020年9月当时动用了上千块显卡算了大概30个显卡年但计算两个100多位数字的成绩你的手机一秒钟不到就能完成这种正确答案难以寻找但验证答案是否正确却很容易的问题随处可见有很多问题的结构就像解一个复杂的密码锁在不知道密码的情况下想找到密码非常困难除了暴力尝试所有的N位密码没有什么好办法但验证密码对不对却很简单把密码拨到需要验证的数字上按下开关看看有没有打开就行了比如说数读填起来要绞尽脑汁但检查答案对不对却很简单只需要把每列每行每个九宫格都扫一遍看看九个数是不是各不相同就行了把很多个数字分成总和相等的两堆要是上千种方案但检查某一种方法是否相等只需要把两堆个子加一遍看看是不是刚好相等就行扫雷也一样根据数字找出地雷很困难但给你一种埋雷的方式对着每个数字验证周围的地雷数量是不是的确等于这个数字却非常的简单这种像老师改卷一样检查判断最终答案是否正确的流程叫做检查程序有些问题写解答程序很难写检查程序却很容易为了刻画这种特性的问题计算机科学家提出了NP问题的概念要完整准确的理解它的含义我们还是得回来认识一下老朋友图灵机图灵机有一条无限长的纸带分成一个个格子每格写一个符号纸带上方有一个读写头内部记着一个状态机器照着一张规则表工作每条规则都写着除在某个状态Q下读到某个符号的时候应该写下什么读写头往左还是往右移动一个状态换成Q片机器的每一步都查表执行直到进入接受或者拒绝的状态可以理解为这台机器最后判断问题有解或者无解我们今天写的任何程序都可以改写成一台图灵机那用这个模型我们就能精确的定义P问题存在一个图灵机和一个多项式P使得对于任意长度N的输入它最多走PN步就会停下来并且给出正确的是或否的答案那什么是NP呢在普通的图灵机里状态和读到的符号一旦确定下一步该做什么就只有一条确定的规则这就是确定性而有另一种神奇的图灵机叫做非确定性图灵机同一个状态读到同一个符号规则表里却可能同时写着好几条规则机器可以任意选择其中的某一条规则行动然后继续只要存在一系列符合规则的选法能够让机器最终走到接受的状态我们就算这个机器接受了这个输入找到了答案这种不确定性正是NP中N的意思Non-Deterministic好多人可能都误解过NP的意思就是Not P这就闹笑话了P怎么会等于不是P的东西呢就拿等和划分这个问题来说非确定性图灵机的程序解决这个问题的流程会非常的妖简直就像是一个神秘的神灵第一段它会从左到右扫过所有的数字每扫到一个就在两条规则里非确定性的选一条在它上面写上0或者1代表这个数字属于左边那对还是右边那对一共做完了N次选择之后第二段则是普通的确定性计算把标了左的数字加起来把标了右的数字加起来比较两个合相等就返回自己找到了答案接受容易理解如果这些数字确实能够分成总和相等的两堆那么1024种悬法里至少能够有一种走到最终接受的状态按照定义非确定性的图灵机就一定能找到这个答案你肯定会问了我哪知道每一次非确定性的分支这个图灵机到底猜了个啥呢诶这就是NP最精髓的地方你可以想象它有一个神奇海螺每一次都能完美的猜对或者你可以想象它在每一个岔路口分身同时探索所有不同的分支最后1024个分身同时去跑第二段的答案检验只要有一个在平行宇宙里找到了答案就算成功第一段只要线性扫一遍部署是N第二段只是普通的加法和比较总和也是N所以整台机器的部署不超过2N当然是输入长度的多项式因此等核划分问题就属于NP了你可以从这个例子里看出非确定性图灵机比确定性图灵机强大得多简直就像开挂一样未卜先知却又在最后死死入口一个问题有简单的检查程序和它能够被非确定性图灵机在多项式时间内接受是一码事因为一旦有一个多项式时间的检查程序只需要在它前面加上一段非确定性的开挂来猜答案整体就变成了一台非确定性图灵机它在多项式时间内解决了问题所以NP问题也可以这么表述当答案为是的时候存在一份能够在多项式部署内确认答案的确正确的凭据容易注意到P里的问题都在NP里因为一个确定性的机器本来就可以看成是一台拥有超强的神奇海螺瞎猜能力但却从不使用的机器既然不用这种非确定性能力都能在多项式时间内用算法找到答案那么拥有了强大的不确定性能力当然更加可以在多项式时间内完成自然是NP的所以P是NP里的一个子集但问题在这两个圈是不是同一个圈呢?这就是P与NP问题能快速检查答案是否正确的问题是否都能快速找到解答本身或者说一个普通的平庸的确定性图灵机能不能有一套神秘的方法可以比肩神明也就是能在多项式的时间内能够得非确定性图灵机指数纷争开挂猜测的能力呢?其实很早就有人问出了几乎一幕一样的问题1956年3月20日一封信从普林斯顿寄出写信的人是库尔特·戈德尔收信的人是约翰·冯诺一曼这时候的冯诺一曼已经确诊了癌症坐上了轮椅几周之后他就住进了华盛顿的沃尔特里德医院在信的开头戈德尔说得知您生病我感到万分难过听说您现在感觉好些了我想冒昧的写信和您谈一个数学问题在此之前人类已经两次撞上了数学的边界1931年戈德尔自己证明有些数学命题是真的但却没法在系统内证明1936年图灵证明有些问题没有任何算法能够解决这封信进一步追问第三件事在那些机器原则上能解决的问题里有多少能够被快速解决呢?信里戈德尔问给一个数学命题和一个数字N让机器判断这个命题有没有长度为N的证明最少需要多少步呢?他把这个步数记作φN他写道如果真的有一台机器φN只是N的长数倍甚至是N平方的长数倍那么尽管存在不可判定性数学家在是非题上的思考工作就可以完全交给机器而且戈德尔认为φN增长的这么慢完全是有可能的只可惜至今我们没有找到冯诺伊曼的回信1957年2月8日他在沃尔特里德医院去世这封信夹在他的文件里30多年没有人注意到直到1988年人们才在美国国会图书馆收藏的冯诺伊曼文件里发现了他其实这正是P与NP问题一份写的足够细的证明检查他对不对是非常机械的我们只需要一行行的核对每一步是否合乎规则就可以这是很快的但想要找到这个证明却要在天文数字一般多的写法里去搜寻这个命题有没有一份不超过100万个符号的证明就是一个NP问题麻烦在于想要严谨的证明NP和P的关系情况是非常棘手的要知道NP是一个无穷大的家族等核划分、数读、分解质因数还有无数惊人都还没有想到过的问题想要证明P不等于NP我们该挑哪一个最难的问题去下手证明它不存在高效算法呢?反过来如果要证明P等于NP难道我们要给无穷多个问题一个一个的去找多项式算法吗?为了解决这个问题理论计算机学科提出了一个极为精妙的概念叫做规约Reduction常常有那种知乎问题问如果我有一种能力能保证考试一定及格那会有多厉害?那我的回答是你将成为历史上最无解的人肉神域基想象一下我可以出一张卷子第一道大题是证明李曼猜想61分剩下来随便出点题加在一块39分然后让你来考试并让你实现这个系统所赋予你的绝对及格之力你要是能及格是不是一定就做出了李曼猜想这道题那用同样的方法任何难题都能塞进这张卷子那千些年难题还剩下五个没有解决咱就出一张卷子是吧一道题二指分满分一百你又一定会及格那么这一场考试结束之后你就一定能解决至少三个佩雷尔曼和华尔斯来了在你面前也是个弟弟这种像黑客一样利用某一套系统能力撬动一个不可思议的结果的过程就叫做规约有了这种规约我们就能明白一定及格这个技能有多强或者说做到这一点有多难它强于任何一个数学问题规约的妙处就在于它能够证明两个看上去毫不相干的问题之间存在着神奇的联系并且我们可以说明一个问题不会比另一个问题更容易比如说解束毒和涂染色束毒大家都听说过九行九列一共81个格子有些格子已经填好了数字要把剩下的格子填满让每一行每一列每个九宫格里一到九都恰好只出现一次而涂染色问题是说给你一张图图中有一些点和连接各种点之间的边的线染色板里有几种颜色问你能不能给每个点都涂上一种颜色让有连边的两个点颜色不相同一个是填数字的游戏一个是给涂染颜色看起来没有任何的联系但接下来我们就会用规约证明染色这个问题是更难的如果你能高效的解决它那么就能直接用这个线成的染色解法轻松解决任何一个数度方法是这样的我们可以把81个格子化成81个点同一行同一列或者同一个九宫格里的两个格子点就用一条线连起来这样每个点都连着20条线我们再把1到9这9个数字看成9种颜色于是把数读填满就等价于用9种颜色给这张图染色这背后的妙处在于根据染色的规则有连边的两个点不能同色而同一行的所有点之间都有连线因此只要完成了染色的要求这一行就自动两两不同色了同理同一列和同一个九宫格里的点两两连线同时保证了每一列和每个九宫格内的颜色是各不相同的所以只要这个图能成功染色我们把颜色翻译回数字一定每一行每一列每个九宫格里的数字都是两两不同刚好覆盖从1到9的那当然了还会有些问题在数读问题里有些格子一开始就填好了数字这就是数读最重要的题面而染色问题里所有的点一开始都是空白的没有预先涂好颜色这一说怎么在一个空白的图里逼迫某些特定节点一定只能是某种颜色呢哎办法是在图的旁边另外加上九个点当做调色盘这九个点两两相连于是它们必须涂成九种不同的颜色正好一种颜色代表一个数字我们可以给调色盘的九个点各标上一个数字那如果数读问题的题面里某个格子一开始就写着五我们就把这个点和调色盘里除了五号色之外的八个点都连起来那么根据染色要求这个点就不能填五之外的任何颜色因为它和这些颜色都相邻了它就被迫只能涂成五号色对所有数读里一开始给定了数字的节点做这样的操作这样一整道数读连同题目所给出的数字就被原封不动的翻译成了一个纯粹的染色问题这张图如果能用九种颜色染好当且紧当这道数读题有几染好之后按颜色把数字读回去就是数读的答案这就意味着如果有人发明了一个能够给任何的图快速染色的算法那么任何一道数读题都可以这样先翻译成一张图交给这个算法染好色再按照颜色读回数字数读也就跟着被快速解决了所以给一张图染色这个问题是比解决数读更难的因为你能解决染色就能本质上轻松的完成数读题或者说染色问题至少和数读一样难绝不会比数读更容易把问题A的任何一道题在多项式部署内翻译成问题B的一道题并且保持答案不变A有解当且简单B有解这就叫做把A归约到BA能归约到B就说明B的难度大于等于A顺着这个思路计算机科学家问出了一个更大胆的问题在NP这个无穷大的家族里有没有这样一个问题家族里的每一个问题都能归约到他身上如果有它的难度就大于等于所有的NP问题至少和所有NP问题一样难它的威力也会大的不可思议只要给它找到一个多项式算法等候划分数读分解质因数染色连同那些所有今天都还没有想到的问题就全都有了多项式算法既然所有的NP问题都有了多项式算法P就等于NP而反过来只要证明这一个问题没有多项式算法那我们就找到了一个确定没有多项式算法的NP问题的例子P就不等于NP所以我们不需要研究无穷无尽的问题我们只需要盯住这个最难的NP问题代表看看到底有没有多项式算法就能直接决定所有NP问题是不是都在P里的命运这样的问题叫做NP完全问题NP Complete Problem可是这种问题真的存在吗无穷多个NP问题包括那些还没有被人想到的问题居然都能翻译成这个问题的某个具体例子规模还不大听上去几乎不可能做到然而1971年人类找到了第一个这样的问题1970年在加州大学伯克利分校当了四年助理教授的斯蒂芬·库克没能从数学系拿到终身教职转而去了多伦多大学第二年5月他在俄亥俄州举行的计算理论年会上发表了一篇论文题目叫做定理证明过程的复杂性多年以后伯克利的理查德·卡普回忆这件事情时写道计算机系计算机系没能说服数学系给库克终身教职是他们永远的耻辱库克证明有一个叫做可满足性的问题satisfiability problem简称SAT是所有NP问题都能规约过去的它的出发点就是非确定性图灵机一台突灵机运行的时候每一步的全部信息纸带上每一个写着什么读写头停在哪一格内部是什么状态可以全部合起来叫一个格局configuration这里方便起见我们把读写头的状态也当成一个格子写在它所在的格子的相邻左边把第0步的格局写成第一行第一步写成第二行一直写到PN步就得到了一张表格这个表格的行数就是运行的部数又因为一步最多移动易格所以列数也不会超过部数的多项式量级整个表格的大小都是多项式的所有的NP问题都能归约到SAT问题的核心原因是任何一个NP问题能最后变成接受状态也就是有解本质上就等于说存在这样一张由一行行格局所组成的表格历史它的第一行写着输入最后一行出现接受状态而中间相邻的每两行都符合规则表的演化规则因此任何一个问题能不能被非确定性图灵机找到解答等价于这中间大片的空白能不能被恰当的填入符号使得整个表格是合法的构成了这个图灵机一步步运行直到找到解答接受的过程其实想要这个表格合法要求也不算很难只关注相邻两行绝大部分的格子应该都和上一步保持一样因为图灵机每一步只会改动读写头所在的那一格所以T加1行的第I格写什么本质上只取决于第T行的I-1I、I加1这三格要么上面一行的这三格根本没看到读写头那就直接复制上一行同一个第I格格子或者出现了读写头的状态那我们就要求局部的变化是符合非确定性图灵机规则的某一条的比如说这里就符合Q1再看到零时可以变成Q3并又一一格写下一的规则所以整张表格合不合法就可以拆成许许多多个小检查每个只看上下两行里一个两行三列的小窗口看它是不是规则表所允许的样子每一个小窗口里只要满足某一条图灵机规则就可以所以是或的关系而所有的窗口都要同时满足检查所以是且的关系最终整个表有没有一种合理的填法就取决于我们能不能填入一系列的0和1能够让一个巨大的表达式成立这个表达式需要在每一个局部都成立每个局部成立的条件都能整理成几条从具而从具成立只需要一系列规则有一个满足就行所以里面都是或的关系没错这就是大名鼎鼎的SAT问题需要填入的格子和整个表达式的长度都是N的多项式把它们写出来也只需要多项式的部署我们前面说过任何NP问题都有一台多项式时间的非确定性机器也就是先猜答案再检验的过程所以任何NP问题是否有解都可以这样规约到画一张表格进而变成一个不而表达式能不能为真的SAT问题一个确定性图灵机从上往下把表格一行行填出来很容易只需要让机械正着跑完就行而只知道最后一行要出现接受和初始的configuration要倒着推出有多种转移规则的中间空白里该怎么写怎么到达却非常困难从这个角度上来说前面说的乘法和分解也很困难是一样的道理你想啊正着算成绩就如同图灵机从上到下一行算到结束一样很容易而根据成绩分解就相当于在术式的最后一行固定成8616460799要你往回倒推一开始该填什么其中每一步都符合乘法术式的规则这就困难的多了顾客还证明这些要求总能改写成每个从具最多涉及三个变量开关的样子这个版本就叫做3SAT不妨把它想成四个开关A B C D和四盏灯每盏灯下面挂一条要求要求里面至少有一项能够成立灯就亮比如说第一条是A打开或者B打开或者C关上第二条是A关上或者B打开或者D打开然后要问你怎么样拨动所有的开关变量才能让所有的灯全都亮起之所以让每个从具都只有三个是为了方便其他问题都能归约到它一个更容易理解3SAT问题的比喻是想象你开了一家咖啡馆要决定各种具体的因素比如说灯是亮还是暗有没有音乐过不过夜等等每个都是一个需要决定的变量而每个顾客会提出针对三个变量的要求满足一个就行比如说要有音乐或者能过夜或者有拿铁之类的客人的要求就是从具而3SAT就是在问是否有一种对咖啡馆各种变量的设计方式能够让所有的从具都成立或者说让所有的顾客一个不差的全都满意容易注意到SAT本身也是属于NP的因为给定一种开关的播法我们逐条检查每条从具是否成立就行所以他正是前面要找的那种问题他自己是NP的但所有的NP问题都能翻译成他这就是人类发现的第一个NP完全问题它是最难的NP问题从这一刻起无穷多个问题被收容到了同一个问题身上几乎同时在莫斯科克尔·莫格洛夫的学生里亚尼德·列文独立得到了同样的结论他的博士论文得到了导师和答辩委员会的认可学位却因为政治原因被当局拒绝授予苏联的研究者把这类问题叫做Belibur意思是穷举 挨个去试列文那篇通用的穷举问题1973年才发表正文只有两页他后来说自己推迟了发表是想把另一个问题也放进去给出一个函数的全部取值找出能算出它的最小电路他没能做到今天这个定理被称作库克毕尔文定理如果说一个SAT问题就能代表所有的NP问题已经让人十分惊讶那么接下来发生的事情则更加不可思议那就是并不只有SAT这一个问题享有这样崇高的地位许多看起来非常简单像游戏一样的问题居然也都是NP完全的第二年1972年的3月在纽约州IBM的研究中心卡普在一次研讨会上报告了21个NP完全问题五花八门比如说一张地图上有许多城市和道路能不能找到一条路线把每座城市恰好经过一次最后回到起点这个问题是NP完全的一群人里谁和谁认识已经知道能不能从中找出K个人彼此都两两认识或者找出K个人两两都不认识这个问题也是NP完全的一台机器要处理一批任务每个任务都有自己的耗时期限和物期罚款能不能排出一个顺序让总罚款不超过某一个数这个问题是NP完全的一个背包能装的重量是固定的一堆物品轻重不一能不能挑出一期差好把背包装满这个问题是NP完全的要用电线把几座指定的城市连起来中途可以经过别的城市能不能让电线的总长度不超过某一个数这个问题也是NP完全的顶点覆盖集合覆盖恰好覆盖团覆盖三维匹配最大额01整数规划等等21个问题全都是NP完全的没想到吧那些看起来像游戏一样的问题其实底层是极为困难的它们和SAT问题享有相同的地位换句话说如果你能高效的解决把一个图染色的问题或者这21个问题当中的任何一个你也就能在多项式时间内高效的解决任何一个NP问题这怎么可能呢染色问题为什么也有这种不可思议的难度是怎么证明的其实原理和之前一样还是规约既然我们已经有了一个最难的无敌NP完全问题3SAT那么只需要证明任何3SAT问题都可以进一步翻译成某个具体的染色问题其节点数量不超过变量数和从具个数的多项式那么通过巧妙的节点设置让这张图能够染色精确的等价于原来的布尔表达式能够取之为真那么任何一个复杂的NP问题都可以先翻译成一个等价的3SAT问题再进一步翻译成一个等价的染色问题你能对任何图染色也就能解决任何一个NP问题于是我们就成功证明了染色问题也是NP完全的在这个过程中你也会发现为什么我们一直强调规约的过程规模不能超过多项式因为只有这样你在不断的迁套过程当中最终的这个问题的规模才能是刚开始问题的多项式那么最终问题的算法也是原来问题的多项式算法该怎么翻译呢我们规定只用三种颜色并且还是一样先用一个三角形构建起一个染色盘这三种颜色分别命名为T F B分别对应于真 True假 Force和一个辅助的颜色对于每一个变量XI我们构造两个节点XI和Not XI将它们和B连成一个三角形那么这样根据连边的两个点不同色的规定那只可能XI和Not XI一个真一个假对这两个节点的染色就相当于对XI这个变量复制那接下来我们就会设计各种辅助节点对于每一个从具L1或L2或L3我们都引入五个辅助节点长成这个样子你可能会问何意味答案是这样设计的目的就是为了确保一个从具素设计的L1、L2、L3三个变量中想要成功的三染色必定至少有一个是真的因为如果三个变量都不成立都是假那么E这个节点只能是B那么D这个节点就只能是假的颜色F可是问题就出现了A、B、C形成了三角形它们的颜色两两不同其中必然有一个是假的颜色F可是现在三个节点都和某个颜色是假的F的节点相连所以它们都不能是F因此矛盾所以这五个辅助节点的设计就非常巧妙的迫使所有从具所对应的三个节点里至少要有一个是真的颜色T就这样对每一个从具都整出这么五个点出来最后把一整个图交给染色机器问它说这个图能不能用三种颜色染色该怎么染那么一旦能够染色成功你再看看一开始那些XI变量的复制情况就得到了一个3SAT问题的解你肯定要问了这五个辅助节点逼迫每个从具都必须成立的操作是怎么想出来的?答案是科学家注意到的达普一口气注意到了SAT问题可以一路巧妙的翻译成21个不同的问题从而证明了它们都是NP完全的我们摇班的算法设计期末考试就成天找一个奇奇怪怪的问题然后让我们设计这样一套归约的翻译过程来证明它是NP完全的到了1979年算法设计的教科书附录里已经收录了约300个NP完全问题到了今天人类已经发现了好几千个NP完全问题遍布流程的统筹芯片设计生物经济学甚至是投票机制设计50多年以来每个领域都有人想要给自己的那个问题找到一个快速的算法但没有一个人成功复杂的理论告诉人类因为它们其实都是同一个问题这几千次失败都是在同一个问题上的失败那它们困难的共同核心到底在哪里呢?SAT给了一个统一的视角和诠释因为这些问题都有许多局部的规则组成每个规则就是一个从具它只关某几个条件之一需要成立可不同局部规则之间缓缓相扣极为复杂的纠缠、偶合在一起它们甚至可能会互相矛盾要让所有的规则同时成立就要在整体上协调一旦一个问题有了这种重口难调的底层特性立刻就会变得极为棘手拥有了NP完全的前置而规约证明的过程就在于怎么发挥这个问题的这种前置将任何一个3SAT问题的实力落实在这种特定问题的具体例子上在喀布之后NP完全问题出现在越来越意想不到的地方比如说2000年英国博明汉大学的数学家理查德·凯伊发表了一篇论文题目叫做扫雷是NP完全的扫雷相信大家都玩过给出一个部分翻开的扫雷局面判断有没有一种埋雷的方式能够让每个翻开的数字刚好对应于它周围八个格子里有几颗雷同一年千禧年大奖刚刚公布数学科普作家伊恩斯托尔就在科学美国人上写了一篇专栏标题叫做百万美元扫雷要证明判断扫雷局面是否自洽是NP完全的我们只需要说明任何一个3SAT要求的清单都可以翻译成一个扫雷局面并且原来的SAT能够被满足当且仅当这个扫雷局面存在一种对应的埋雷方式整个设计的起点起源于一个扫雷里经典的名场面那就像是这样所有的地方都完事了只剩下最后两个格子生死二选一哪一个有雷都会满足整个条件但没有任何其他的信息能够帮你判断到底在哪儿只能生死二选一在你点下去之前这颗雷像薛定额的猫一样在左边和在右边两种可能都会同时成立数学家就想到利用这一点可以正好拿来当一个0和1的开关如果X有雷这根导线传递的就是高电频1如果是XP有雷那么这根导线传递的就是低电频0凯伊接下来展示了巧妙的设计可以让一个局部的二选一的量子叠加态不断传递让好多个量子叠纠缠在一起形成导线一样的结构具体的构造是这样的中间一行按XXP1的顺序一直重复X和XP是一对未翻开的格子后面跟着一个翻开的1紧接着它的上下两行全是翻开的1再往外面两行都是翻开的0上下两行的1保证每一对X和XP里恰好有一颗雷这就是一个二选一而夹在两对之间的那个1又保证前一对的XP和后一对的X里恰好有一颗雷所以只要有其中任何一对的可能性坍缩比如说XP有雷那么下一对的X就不可能有雷所以下一对只有XP有雷那再往下一对也一样就这样一瞬间整根导线到底是X有雷还是XP有雷就被同时确定了整根导线上的叠加态被穿在了一起凯一还通过设计让导线可以拐弯也可以分叉出好几个接头甚至能让两根导线在平面上互不影响的交叉接着凯一还为这种逻辑电路设计了一整套逻辑门也就是说通过设计周围数字的结构让导线里的量子态取反通过这样的扫雷顺序你就会发现经过这个结构之后导线内部从X有雷变成了XP有雷这就是飞门有了飞门凯一还造出了羽门输出量子态是两者的end有了羽门和飞门也就有了货门输出是两根导线结构的or有了这套零件就可以把任何一张3SAT要求的布尔表达式编译成一个扫雷局面而这套过程可能是所有规约里含义最直观的因为我们真的就是把3SAT里所对应的布尔电路在扫雷的板子上给它搭出来每个开关的变量就是一根输入的线每条从具要求对应于两次货门它会接入每个变量或者变量经过飞门的取反比如说这个X1 or X2 or NOT X4就会是这个样子如此一个货门的输出就是这个从具是否满足的结果我们接着把所有从具的导线全部用且门接在一起最后把最终的输出接入一个强迫必须为真的终端好了 构造完成 请您扫雷你会发现这样拼出来的扫雷局面要找到一个和所有数字都对得上的埋雷方式本质上就要求你给出每一个一开始的开关变量的具体取值使得在每个逻辑门和电线位置都是自洽之后最终输出真的结果所以如果真的存在一个完美高效的扫雷专家他在这种具体问题里略失拳脚就能轻松解决SAT问题所以扫雷不比SAT问题容易也就至少和所有的NP问题一样难扫雷本身使NP问题则更容易了给出一种具体的买雷方式之后逐个核对每个数字是不是满足是很快的当然也是多项式的所以扫雷也是一个NP完全问题如果你能在多项式时间内解决扫雷你就能解决任何一个NP问题在那之后人类在各种千奇百怪的游戏里都构造出了这样的导线和逻辑门数读、德罗斯方块、超级马里奥、唐果传奇从而证明这些游戏底层都蕴含着人类最困难的计算问题的复杂性在这里我们就需要进一步纠正一个很常见的误会一个问题是NP完全的并不意味着人类拿起它就会束手无策我们只能干瞪眼暴力枚举事实上我看到过很多小游戏它们底层都是NP完全问题也就是确保这些问题没有高效的系统的通用解法看起来又很简单很有趣从而最大程度的调动用户的兴趣消耗时间并且在玩家卡壳的时候让他们点击广告比如说这个这个还有这个有些甚至比NP问题还难是PSpace完全的大家照样玩的开开心心能够解出一关又一关这是因为就算P不等于NPNP完全问题的很多具体例子在现实里也常常能有一个比较高效的特别解法或者是启发式算法因为NP完全说的是最坏的情况没有一个算法能够在所有题目上都快可现实里的题目大多都有结构比如说找一条总路费成本最低的回路把每个点都恰好过一遍这叫旅行商问题是经典的NP完全问题可2025年人们算出了韩国8万多家酒吧之间的最短巡回路线还证明了它确实最短因为这些酒吧散落在真实的地图上距离有很好的几何结构求解器能够减掉绝大多数走法芯片公司每天也都在用SAT求解器处理着带着上百万个开关变量的复杂逻辑要求清单这也是因为这些变量之间的纠缠并没有达到理论上最复杂的程度所以实际的可解性很强要是我们能够放松每个层距差一个都不行的要求转而追求满足尽可能多的层距那么纯随机的方法更是能在7万亿下满足7%的层距可是对于能全部满足的式子这个87.5%的比例也就是极限了如果有算法能够做到比它再多一点点比如说确保能够满足超过0.8750001的层距那么NP就会等于P这背后的原理非常复杂我们就不在这一期视频里展开了假如P真的等于NP而且那个算法够快世界会怎么样呢?计算机科学家斯克·阿伦森写过一段话大意是如果P等于NP那么能欣赏交响乐的人都会立刻成为莫扎特能跟上一步步论证的人都会成为高斯在那个世界里老手和新手没有区别我们说一个人经验丰富直觉好有品位说的其实是他能够在指数多的可能性里比别人更快的找到对的那一条路要是找到和验证一样容易只要你能认出好的答案你就能找到他经验和直觉也就不在之前与此同时如果P等于NP密码学也会随之消失网上几乎所有的加密都建立在正着算容易而倒着推很难的基础之上比如说两个技术相乘容易分解困难椭圆区限格密码也是同样的道理2024年刚刚定下的所有抗量子标准都不例外如果任何正着算很快的过程都能迅速的被快速倒推这些密码也就全都不靠谱可以被高效的破解正因此绝大多数研究者是相信P不等于NP的计算机科学家加萨奇做过三次调查认为P不等于NP的人从2002年的61%涨到2012年的83%再到2019年的88%当然了也有人压另一边比如说写过计算机程序设计艺术的高德纳就说他渐渐相信P等于NP只不过那个多项式的次数可能大得无法想象证明也多半给不出具体的构造性算法为了P与NP人们交过很多份答卷荷兰数学家沃金泽维护过一个网页收落116份宣称解决了这个问题的论文61份说等于49份说不等于但最后没有一份站得住脚全都有各种各样的问题比如说2010年8月惠普实验室的研究员德奥拉里卡尔把一份P不等于NP的证明发给同行几天之内世界各地的专家在博客上逐行检查阿伦森公开表示如果这份证明先拿到克雷奖他就自逃20万美元追加奖金结果一周左右证明里的漏洞就浮出了水面这还是一场炸糊为什么证明这么难呢?回想之前的视频我们讲过如何证明齿规做图无法做出三次根号二数学里想要证明一类方法不可能达成某一个目标需要对所有这样的方法进行最精练的本质概括比如说齿规做图本质上就是拿着整数做四则运算和开根号再基于这样的本质总结出它能力的边界也就是二次扩域并证明目标在边界之外可是P不等于NP这个问题本身却带有一种悖论式的困难性因为某种意义上人类能够想到的算法和智慧的边界都是P的也就是按部就班按照某种确定的规律法则执行比较少的多项式次数得到答案可我们居然要证明所有我们未曾想到的无穷多的算法都不可能高效解决某一个问题这就好比一个小孩说我只会数数但我能证明人类的ZFC公理体系不可能证明黎曼猜想也要荒唐人类目前对所有的多项式算法的建模是逻辑电路一个能在多项式部署内解决的问题都能用多项式个逻辑门的电路算出来最底下一排是输入每个输入是0或者1往上是一层层逻辑门比如说雨或飞门门和门之间用导线连起来最顶上的那根线突出答案一个电路有复杂取决于它用了多少个门计算机运行一个算法每一步不过是根据内存的上一刻状态算出下一刻状态而这一步本身就能用一小座门来搭出来把运算过程一步一步的展开再挪起来就会得到一个电路算法跑多少步电路的门数大致就是部数的平方所以凡是能在多项式部数内解决的问题都能用多项式个门的电路解决反过来只要证明某个NP问题需要的门多到超过任何多项式就证明了P不等于NP这就是目前P和NP问题研究的前沿领域叫电路复杂度Circuit Complexity按理说复杂的电路函数应该多的是1949年湘农做过一个数数的论证N个输入的布尔函数也就是给每一种输入组合指定一个0和1一共有2的2的N此方此方者是一个双重的指数可门数量有限的电路能拼出来的花样远远没有这么多所以绝大多数的函数都会需要N分之2的N此方这么多个门是指数级的也就是说随手抓一个函数它几乎一定是很难计算的可直到今天对一个具体的函数人们在一般电路下能够证明的最好的下界只有大约3.1N个门这个记录是2022年两位清华摇班的本科生李家图和杨天琪创下的之前的记录是3.01N左右然而即便如此从3.1N到超过任何多项时中间依然隔着遥不可及的鸿沟这些年里人们对NP完全问题或者说更具体的3SAT问题有多难还提出过一个比P不等于NP更具体的猜想叫做指数时间假设简单来说这个假设不仅认为NP完全问题不存在多项式算法还给这个算法需要的部数一个具体的下界那就是至少需要指数部的时间无论是判断一个不而表达式是否有结果为真的变量复值还是我们一开始所讨论的等和划分问题本质上我们都逃不开指数级别的尝试过程我们不一定真的把所有可能一一的试变但它至少得是一个指数1.3的N次方1.1的N次方总归是某个C的N次方这堵墙似乎总是躲不开3SAT这样的NP完全问题必须要指数的时间才能够完成这就是指数时间假设Exponential Time Hypothesis还有一个更强的假设叫SETH它假定这个指数必须是2的N次方人类科学家几乎都相信它是真的如果一个密码所不同的密码之间没有联系那我们最坏情况下不是肯定要一一尝试所有的指数量级的密码才行吗然而2026年10月26日OpenAI在公开的数学成果记录里画出了一份手稿标题就是指数时间假设是错的这份手稿声称它找到了一个确定性的算法可以在比指数更快的时间里精确的数出任何一个具体的3SAT问题有多少个输入使得表达实为真不过这个快的程度不是很大也就是从2的N次方变成了2的0.logn分之N次方指数上多除以了一个0.n左右的数但在量级上它已经比任何C的N次方都要快截至目前证明还没有经过同行审查一个由英帕利亚佐帕图里和威廉姆斯牵头的独立小组正在审查而这些人正是当初提出指数时间假设的人如果它成立几十年来许多以这个假设为前提断言某某问题不可能更快的结论都要全部重新审视几百篇以这个假设成立为基础的论文地基前提完全垮它所有的结论都要全部推到重新来考察这意味着当N去向于无穷大时有一种神秘的方法可以通过一次变量开关的设置系统性的测试一大堆不同变量组合的可能性这对于一直相信指数时间假设为真的整个理论计算机科学家来说是完全不可思议的虽然这个算法还没有快到多像式所以不能证明NP等于P但NP问题的难度已经发生了松动指数复杂度这堵墙已经被打开接下来会发生什么我们不得而知那数学证明不了大自然会不会替我们算出来呢有一种说法流传了很久说肥皂膜总会收缩到面积最小的状态所以把它张在几根钉子之间他就能找出连接这些钉子的最短网络而这是一个NP难的问题叫做斯坦那树问题2005年阿伦森真的做了这个实验他用几块玻璃板夹住几根铜钉静静肥皂水再提起来三四根钉子的时候肥皂膜通常能够找到最短的网络但也并不总是这样钉子一多它常常停在更长的形状和不好的局部计较之上有时还会出现三条膜围成的小三角形这在最短的网络里根本不可能出现同样的装置再进一次得到的形状又不一样肥皂膜只会停在附近最短的形状上它也会卡在局部最小指计算机科学家阿伦森在他2013年出版的一本书中提出也许应该把NP完全问题在物理世界里没有高效的解法当作一条物理原理来看待就像润力学第二定律一样涌动机造不出来它没有被证明可到今天为止无论是电脑肥皂膜还是我们正在构建的量子计算机都没有让它打破这个规则如果这条规律成立我们所住的就是一个找答案比验证答案要难得多的宇宙而正是因为难秘密才能守得住一个好的想法才会珍贵一个人的经验直觉和洞见才有它的分量如果NP真的等于P而且这个算法还非常高效不是N的两万次方这种那这个世界将会变得无比令人兴奋但也恐怖至极以上就是NP和P问题的科普作为本科专业就是理论计算机的摇班毕业生这期视频倾注了我大量的心血如果你觉得这些内容有意思希望你能够点赞支持一下之后我还会做更多这样的科普一定要记得关注我满是陈思路学汉引路不辛苦我们下期再会我们下期再见我们下期再见我们下期再见