OpenAI论文挑战指数时间假设 计算界重估P与NP鸿沟

OpenAI论文挑战指数时间假设 计算界重估P与NP鸿沟 物理规律与计算复杂度的不对称性决定了寻找解答注定远难于验证答案，若P等于NP将直接摧毁现代密码体系与创造性劳动的价值根基。 视频系统性地拆解了千禧年大奖难题中最为深刻的“P 是否等于 NP”（P vs NP）问题。作者从等和划分等任务的指数爆炸与渐近复杂度（大 O 记号）切入，阐明了确定性多项式时间（P）与非确定性多项式时间（NP）在求解与验证上的核心不对称性。随后，视频深入梳理了从哥德尔给冯·诺依曼的绝笔信、库克–列文定理到卡普 21 个 NP 完全问题的理论演进，生动展示了数独、图染色与扫雷等问题的精妙归约机制。最后，作者结合电路复杂度下界、2026 年 OpenAI 关于突破指数时间假设（ETH）的最新前沿手稿，以及肥皂膜实验等物理视角，探讨了这一问题对现代密码学、自动化证明与人类认知哲学的根本颠覆。 P 与 NP 问题的核心是寻找答案与验证答案的非对称性：若 P=NP，现代加密体系将彻底崩溃，定理证明亦可全自动化；若 P≠NP，则确立了宇宙中寻找答案注定比验证难得多的根本法则。 (0:00) 库克–列文定理证明了布尔可满足性（SAT）是首个 NP 完全问题，随定理确立的“归约”思想证明数独、扫雷、图染色与背包问题等数千个难题在最坏计算难度上完全等价。 (37:14) 面对一般电路的具体布尔函数，当前人类能证明的门数下界仅为约 3.1n（2022年清华姚班学生打破），距离证明 P≠NP 所需的超越任意多项式界限存在巨大理论鸿沟。 (60:14) 2026 年 10 月 OpenAI 发布手稿，宣称提出一种复杂度为 2^(n/√log n) 的确定性计数算法，虽未证明 P=NP，但直接挑战并可能瓦解数十年来作为基石的指数时间假设（ETH）。 (65:30)

清华大学姚班毕业生漫士系统梳理了计算复杂度理论的核心命题“P 是否等于 NP”，指出寻找答案与验证解答之间的非对称性构成了现代密码学与认知秩序的基础，而跨越这一鸿沟仍面临着巨大的数学与物理屏障。 指数爆炸与多项式时间闭包 (2:15) 在计算任务中，求和与排序等问题的步数随输入规模按多项式增长，而等和划分等任务的穷举复杂度达到 2ⁿ。面对指数级增长，单纯提升硬件速度几乎无济于事：全球顶级超算耗费数万年也无法算完规模为 100 的等和划分，若增至 200 则直到宇宙终结也无法穷尽。理论计算机科学以此确立了基于最坏情况的大 O 渐近复杂度分析。 所有能在多项式时间内求解的问题集合被定义为 P。埃德蒙兹等人将其确立为高效算法的标准。多项式时间具备代数闭包特性，子算法嵌套后依然是多项式，保障了算法模块化的健壮性。虽然人类直觉常将复杂问题误判为无法快速求解——如归并排序打破冒泡排序、哈奇扬用椭球法证明线性规划属于 P、AKS 算法证明质数判定属于 P——但要排除所有潜在算法的存在，必须依靠严格的数学证明。 验证的不对称性与 NP 完全问题 (21:08) 许多核心计算问题展现出极强的不对称性：求解极其困难，但核验给定的答案却能在多项式步数内完成。基于确定性图灵机与非确定性图灵机的抽象，NP（非确定性多项式时间）被严格定义为可在多项式时间内验证解的问题集合。哥德尔早在 1956 年致冯·诺依曼的绝笔信中便敏锐指出，若机器验证与证明能够同样高效，数学家在是非题上的思考就能完全交给机器。 为了判定 NP 家族的整体难度，理论界发展出“归约”工具。库克与列文在 1970 年代初独立证明了布尔可满足性问题（SAT/3-SAT）的通用性：任何非确定性图灵机的多项式时空演化表均可编码为 CNF 范式。若一个 NP 问题能被所有 NP 问题在多项式时间内归约，它即为“NP 完全问题”（NP-Complete）。理查德·卡普随后证明哈密顿回路、背包问题、独立集和图染色等 21 个经典问题均为 NP 完全问题。这类问题的共同本质在于局部约束环环相扣，全局协调面临极高难度。 现实映射与电路复杂度鸿沟 (52:45) NP 完全结构不仅存在于理论推演中，还广泛渗透在扫雷、俄罗斯方块等休闲游戏里。理查德·凯伊在 2000 年证明，扫雷局面可通过逻辑门构造完整编译 3-SAT。虽然最坏情况下算法受阻，但现实中的问题往往具备空间几何度量或弱纠缠特性，使得现代 SAT 求解器和巡回路线算法能处理上万甚至百万级变量。不过根据 PCP 定理推论，近似求解同样存在硬性界限，如 3-SAT 满足率超过 87.5% 便等价于证明 P 等于 NP。 当前主流学界压倒性地倾向于 P ≠ NP。攻坚该问题的核心工具是电路复杂度。香农在 1949 年用非构造性计数证明绝大多数布尔函数都需要指数级数量的逻辑门，但针对特定具体问题证明下界进展极缓。截至 2022 年，清华姚班本科生李佳图与杨天祺创下的具体函数门数下界仅为约 3.1n，距离证明超越多项式界限 n^k 仍横亘着无法逾越的鸿沟。 指数时间假设冲击与物理极限 (65:30) 比 P ≠ NP 更精细的“指数时间假设”（ETH）断言 3-SAT 的最坏求解时间无法突破 cⁿ（c > 1）的底线。然而，OpenAI 于 2026 年 10 月发布题为《指数时间假设是错的》的手稿，声称提出了一种确定性算法，将 3-SAT 的计数复杂度压低至 2^(n/√log n)，在渐近意义上突破了纯指数下界。目前该成果正由 Impagliazzo、Paturi 与 Williams 等学者牵头的专家组严格审查。若结论属实，大量奠基于 ETH 的算法下界结论都将面临根本性重估。 面对数学证明的僵局，阿伦森在 2005 年通过肥皂膜求斯坦纳树的物理实验证实，肥皂泡同样容易陷入局部极小值甚至形成无效结构。物理系统并不能走捷径绕开计算复杂度。阿伦森提出，或许应当把“物理世界中不存在高效求解 NP 完全问题的机制”视为一条类似热力学第二定律的物理宇宙基本法则。 P 是否等于 NP 悬置了半个多世纪。若 P 等于 NP 成立，现代公钥密码体系将彻底瓦解，直觉、审美与创造性劳动的独占价值也将失去保护；而若 P 最终不等于 NP，则确立了宇宙间寻找答案注定比验证答案困难的铁律。

[60:14] 斯科特·阿伦森: 如果 P 等于 NP，那么能欣赏交响乐的人都会立刻成为莫扎特，能跟上一步步论证的人都会成为高斯。 [2:15] 漫士: 本质上，尽管计算机一直在变快，可面对算法层面上的指数增长的恐怖趋势，硬件计算速度的提升几乎可以忽略不计。 [69:36] 漫士: 正是因为难，秘密才守得住，一个好的想法才珍贵，一个人的经验、直觉和洞见，才有它的分量。

[0:00] 赚一百万美元，最简单的方法是什么？我不知道。 [0:03] 但我知道最难的方法：那就是解决一道数学题，P 是否等于 NP。 [0:09] 它是七个千禧年大奖难题里表述最短的一个，却可能是人类提出过的最深刻的数学问题，没有之一。 [0:17] 它的源头，是人类最古老的一门智慧——算法，和最年轻的工业革命的发明——计算机，在二十世纪中叶的相遇。 [0:27] 这一百万美元，就藏在这一局扫雷里。 [0:30] 如果你能找到一个又快又通用的办法，根据任何一个扫雷局面判断出所有没有雷的方块，这笔奖金就归你； [0:39] 反过来，如果你能证明这样的办法根本不存在，奖金也归你。 [0:45] 同样的一百万，还藏在数独、俄罗斯方块、快递车的路线，甚至蛋白质折叠的方式里。 [0:53] 如果答案是 P 等于 NP，今天保护网上银行和聊天记录的加密算法，原则上都能被攻破，数学家的大部分工作也可以交给机器。 [1:04] 如果答案是不等于，就说明我们的宇宙里有一条规律，有些问题，找到答案就是比检查答案难得多，难到再快的计算机也追不上。 [1:16] 五十多年过去，没有人能回答它。为什么会这样？ [1:20] 到底什么是 P 和 NP 问题？ [1:23] 作为本科专业是理论计算机的姚班毕业生，我一直想做一期视频好好讲讲 P 和 NP 问题，那么它来了。 [1:30] 这将是你见过最系统、最深入浅出、最专业也最有趣的关于NP和P问题的科普，没有之一。点赞收藏，数学启动。 [2:15] 这里有十个数。 [2:17] 我们一共有四个任务：把它们加起来；找出最小的那个；从小到大排好序； [2:23] 最后，把它们分成两堆，让两堆的和相等。 [2:27] 求和最省事，从第一个数开始依次往后加，加上九次，就得到了总和 508。 [2:34] 找最小的数也不难，让数字两两比较，小的留下来再和下一个比，像打擂台一样，一共要比九次，留在台上的 16 就是最小值。排序要多费一些工夫。 [2:47] 最朴素的办法是每一轮都从剩下的数里找出最小的那个放到前面，第一轮要比九次，第二轮比八次，以此类推，一共要比 45 次。 [3:00] 第四个任务就不一样了。 [3:02] 总和是 508，一半是 254，我们要从十个数里挑出一组，让它们的和恰好等于 254。你可以暂停试一试。 [3:15] 答案是 19、22、51、78、84 分到一堆，16、29、56、60、93 是另一堆，两边都是 254，而且这是唯一的分法。 [3:26] 找一个人类来做这道题，多半是凭感觉去凑，结果不对再换另一个分组尝试； [3:33] 电脑没有感觉，最直接的办法是把所有挑法挨个试一遍。 [3:38] 每个数都有进左堆和进右堆两种去向，十个数就有 2 的 10 次方，也就是 1024 种挑法。这样也能找到答案。 [3:49] 这四个任务的难度差在哪里？ [3:53] 我们来看看，当数字的个数 n 变大时，需要的步数是怎么增长的。 [3:59] 求和与找最小值，大约要 n 步； [4:02] 朴素的排序，大约 n²/2 步； [4:05] 而把 n 个数分成总和相等的两堆，这个问题则要困难得多，它在计算机科学里有个正式的名字，叫等和划分问题，是子集和问题 subset sum 的特例。 [4:18] 一个个试要试 2 的 n 次方种分组方法。 [4:22] 把数字的个数从 100 个变成 101 个，求和只需要多做一步，排序的步骤只多出 2% 左右； [4:30] 但等和划分却不同，原来的每一种分组方法，都要再分别考虑新来的这个数放进左堆还是右堆，工作量整整翻了一倍。 [4:40] 每多一个数就翻一倍，这就是指数增长。 [4:44] 对于一个算法来说，指数增长的速度是非常可怕的。 [4:48] 就比如这个等和划分问题，用一台每秒运算十亿次的电脑，30 个数只要算 1 秒，但 60 个数要算上 36 年，要算明白 100 个数，需要的时间会超过地球的年龄。 [5:03] 即便换成今天世界上最快的超级计算机，每秒运算两百多亿亿次，计算 n = 100 也要算将近两万年，如果数字多到 200 个，最强的超算到宇宙终结也算不完答案。 [5:19] 本质上，尽管计算机一直在变快，可面对算法层面上的指数增长的恐怖趋势，硬件计算速度的提升几乎可以忽略不计。 [5:30] 把电脑运算速度提高一千倍，同样时间内，排序算法能处理超过 30 倍的数据量，但 2ⁿ 的等和划分算法却只能多处理 10 个数，因为对于 2ⁿ，函数值增长 1000 倍只能让自变量增加 10。 [5:49] 1971 年世界上最快的计算机每秒最多运算三千多万次； [5:53] 今天最快的每秒两百多亿亿次，五十多年里快了大约六百亿倍。 [5:59] 然而对于等分两堆这个问题来说，只不过从一秒内能处理 25 个数，变成能处理 60 个数，多分 35 个数而已。 [6:09] 一个算法究竟需要运行多久，随着数据规模的增加需要的时间会怎么变化，构成了理论计算机科学最核心的学科：计算复杂度分析。 [6:23] 要知道，分析算法复杂度是一个很麻烦的事情。 [6:26] 因为面对各种不同的数据，算法到底需要多少步是非常复杂的。 [6:32] 就比如等和划分问题，有时运气好，第一次尝试就成功了； [6:36] 有时运气不好，要一直试完所有的排列组合才发现根本不可能，那我们就把 2ⁿ 个所有子集全过了一遍。 [6:45] 因此，当我们说一个算法要走多少步，指的通常是最坏的情况。 [6:51] 算法的复杂度，取的是所有长度为 n 的输入里步数最多的那一个，这样得到的数字就是一个保证，经过这么多步一定有结果，因为最坏情况下也就只有这么多步。 [7:04] 但是问题接踵而至。 [7:05] 这个最多的步数写成 n 的函数，往往长得很复杂很啰嗦，比如 3n² log n + 5n + 7，甚至很多情况下，我们根本无法得到一个精确解析的表达式，找到算法的最坏情况非常困难繁琐，该怎么办呢？ [7:23] 于是，计算复杂度理论从一开始就忽略次要矛盾，只关心它增长的快慢。 [7:29] 比方说，假如有另一个算法的复杂度是 n³ − n，我们想比较它和之前那个算法哪个更好。 [7:36] 此时，我们可以把 x 轴不断缩放再缩放，你会发现当 n 特别大的时候，明显第二个算法的步数更多，这本质上是一个类似比值极限的式子，第一个复杂度最主要的项是 3n² log n，而第二个则是 n³，这两个式子的比值趋于 0，所以前者步数更少，速度更快。 [7:58] 以上这套思路就叫做渐近复杂度分析，1970 年代初，约翰·霍普克罗夫特和罗伯特·塔扬将“最坏情况下的渐近复杂度”确立为分析算法效率和好坏的核心标准。 [8:12] 学过泰勒展开的小朋友肯定见过结尾的大 O 记号，而它正是渐近复杂度分析的核心方法。 [8:18] 当我们说一个函数 T(n) 是 O(n²)，意思是能找到一个常数 c，从某个位置开始往后，T(n) 就永远不超过 c 乘以 n²，好像被 c·n² 这条曲线从上方压住了。 [8:32] 3n² + 5n + 7 就是这样，n 大于等于 7 以后，它始终在 4n² 的下面。 [8:39] 这种记号的好处就是牢牢抓住整个算法最核心的步骤数，系数和低次项都被这个常数 c 吸收掉了，决定增长的只有次数最高的那一项。 [8:51] 用这种说法，求和与找最小值算法，在最坏情况下也只需要线性于 n 的次数，所以复杂度是 O(n) 的； [9:00] 而朴素的每次找最小值的排序，最坏情况下需要 n(n − 1)/2 步，最高项是平方，所以这个算法的复杂度是 O(n²)。 [9:10] 它们的共同点就是都能被 n 的某个常数次方压住，这叫多项式增长。 [9:17] 与之形成鲜明对比的是，等和划分的 2ⁿ 就不行了，不管把 c 取得多大、把次数 k 取得多高，2ⁿ 迟早会冲到 c·nᵏ 的上面，这叫指数增长。 [9:32] 指数的底数哪怕只比 1 大一点点，结果也一样。 [9:41] 关注一个算法需要的总步数，在人类的数学研究中历史悠久。 [9:46] 公元前 300 年前后，欧几里得的《几何原本》就记载了求两个数最大公约数的辗转相除法，这个算法今天仍是加密程序里的常用工具。 [9:57] 1844 年，法国数学家拉梅证明，辗转相除需要做的除法次数，总是不超过较小那个数位数的五倍，一个一百位的数，也不过几百步。 [10:11] 这个结果常被看作算法复杂度分析的开端。 [10:15] 在没有计算机的年代，人手能算的规模很小，多项式和指数的差别，不过是算得久一点和算得更久一点。 [10:24] 然而当计算机把 n 推到了成千上万，这个差别变成了几秒钟与永远。 [10:30] 1965 年，在美国国家标准局工作的数学家杰克·埃德蒙兹，在一篇讲图上匹配算法的论文里，专门写了一节题外话，讨论什么样的算法才算好。 [10:43] 他的回答是，难度随问题规模按代数式，也就是今天说的多项式增长的算法是好算法； [10:52] 而那种显而易见的穷举，难度是指数增长的。 [10:56] 同一年前后，科巴姆、哈特马尼斯和斯特恩斯也在各自的论文里用同样的方式给计算的难度分级，计算复杂度理论（computational complexity）由此诞生。 [11:10] 能在多项式步数内解决的问题，被归成一类，叫作 P，取自 polynomial，多项式。 [11:18] 求和、找最小、排序，都属于 P，它们通常被认为是比较简单的问题，因为存在好的高效的多项式算法。 [11:28] 你可能会质疑，多项式一定更快更好吗？ [11:32] 如果一个多项式算法要 n 的一万次方步，另一个指数算法只要 1.0001 的 n 次方步呢？ [11:39] 那在很大的范围里，后者不是反而快得多吗？ [11:43] 对这个问题，计算机科学家的回答是实用主义的：现实中一般没有这么极端的例子，绝大部分算法问题，多项式算法的次数至多是 n⁶ 左右，而指数算法基本都是 2ⁿ 这样的量级。 [11:57] 在 n 大的时候基本就是多项式算法能算得动，而指数算不动。 [12:03] 除此之外，还有一个更深刻的原因。 [12:07] 一个高效的算法的特点是，不需要像暴力破解密码锁那样对每个变量逐一尝试，而是用有限层嵌套的循环、精巧的中间变量和递归的分治流程解决问题。 [12:20] 它们的共有特点是只做了有限次的加法和乘法，从数据规模n开始，有限次的加法和乘法的结果总是n的多项式。 [12:31] 如果一个多项式算法流程A的每一步是另一个算法B，而B也是多项式，那么总的复杂度就是两者的嵌套，把A里的每个n都换成B的多项式，而多项式的嵌套还是多项式。 [12:46] 从这个角度来说，多项式复杂度这个概念同时也在刻画一种闭包的概念，任意两个高效算法的串行、并行或者复合，其整体流程仍然被视为是一个高效算法。 [13:01] 那么问题来了，把一堆数字分成总和相等的两堆这个等和划分问题，是否属于 P 呢？ [13:08] 到目前为止，我们确实想不出比一个个尝试所有组合更好的办法，而这需要遍历这个集合所有的子集，是指数级别的复杂度。 [13:18] 可想不出好办法，不等于不存在。 [13:22] 有没有可能是我们太笨了呢？ [13:24] 是否会有一个聪明精妙的多项式方法，只不过人类这么多年都没有想到过？ [13:33] 这样的事不是没有发生过，我们不能总是太相信人类科学家叫苦叫难，好多前人声称困难没有办法的问题，经常最后发现有更高效的算法。 [13:47] 就比如刚才说的排序，其实就有比平方更快的做法。 [13:51] 我们可以每次把数字分成两堆，让每一堆各自从小到大排好序，那么此时最小值只可能出现在这两列数字最前面，其中的较小值就是所有数字的最小值，我们把它拿出来放到结果数列里。 [14:10] 经过这样的操作之后，剩余数字的最小值依然只可能在两列数字的最前面出现，我们可以再找出其中较小值，继续接在结果数列的后面。 [14:22] 重复这个安排的过程 n 次之后，我们就能把所有数字排好序了。 [14:28] 这个合并的过程只需要 n 次操作。 [14:31] 你可能会说，这是耍赖啊，这两堆数字各自还得内部排序，这个时间又怎么算呢？ [14:37] 答案是，可以用完全相同的办法层层向下递归。 [14:41] 比如，1 级代理负责一半数字的排序，它将这一半的数字进一步分成两堆交给 2 级代理排序，自己再用 n/2 的时间归并。 [14:56] 你可能会问，那 2 级代理又如何排序呢？ [14:58] 答案是再找 3 级代理排好序，然后自己合并。 [15:02] 因为每次向下代理任务时，数字的规模都会减半，所以在 log₂ n 次代理之后就只剩下一个数了，这一级代理什么都不用做直接返回。 [15:14] 同一级所有代理，每人会单独处理一小段合并，它们各自操作的步数就是负责的长度，加一块刚好等于数字总数 n。 [15:25] 所以一层层累加 log n 级代理需要的操作步数，每一级 n 步，一共就只需要 n log n 步就能完成排序了。 [15:36] 这叫做归并排序，由冯·诺依曼提出。 [15:39] 我们前面说过，朴素的每次找出最小值的选择排序最坏情况下需要 O(n²) 的步数，而归并排序只需要 O(n log n)。 [15:49] 这带来了巨大的效率提升，普通家用电脑 1 秒大约十亿次运算，用选择排序只能给几万个数字排序，而用归并排序则能在同样时间内完成几千万个数字的排序。这就是算法优化的威力。 [16:07] 类似的事不止发生过一次。 [16:09] 高中数学里学过线性规划，比如在（x ≥ 0、y ≥ 0、x + 2y ≤ 8、3x + y ≤ 9）这几个线性不等式的条件下，求 2x + 3y 的最大值。 [16:17] 每个一次不等式都在平面上划掉一半，全部相交之后，剩下的区域是一个凸多边形，叫作可行域； [16:26] 把直线 2x + 3y = z 往右上方平移，它离开可行域之前碰到的最后一个顶点 (2, 3)，给出了最大值 13。 [16:36] 工厂排产、物资调运、航班排班，本质上都是这样的问题，这就是线性规划。 [16:44] 只不过真实场景变量有成千上万个，此时可行域会从多边形变成高维空间里的一个凸多面体。 [16:54] 该怎么解这种高维空间的线性规划最优解问题呢？ [16:58] 1947 年，美国数学家丹齐格提出了单纯形法，从可行域的一个顶点出发，沿着棱走到目标值更大的相邻顶点，一步一步爬到最优的那个。 [17:11] 它在实践中非常好用，可是 1972 年，克利和明蒂构造出一类特别刁钻的难题，能让单纯形法把 2ⁿ 个顶点挨个走一遍。 [17:23] 单纯形法在最坏情况下需要指数的复杂度。 [17:28] 那线性规划是不是就不存在多项式的高效算法，不在 P 里呢？ [17:33] 不一定，虽然单纯形法最坏情况下需要指数复杂度，但其他算法可能可以在多项式步数内解决问题。 [17:42] 可是这样的算法是否存在呢？这个问题一时成了悬案。 [17:47] 1979 年，苏联数学家哈奇扬给出了答案。 [17:51] 他提出了椭球法，不去在顶点之间一步步跳转，而是先用一个很大的椭圆把可行域整个包住，然后检查椭圆的中心。 [18:03] 如果中心满足所有的不等式，就找到了一个可行点； [18:08] 如果某一条不等式不满足，可行域就只可能落在过中心、和这条不等式边界平行的那条直线的一侧。 [18:15] 于是把椭圆切成两半，只留下可行域所在的那一半，再用一个更小的椭圆把这半个包住。 [18:24] 每做一次，椭圆的面积都按固定的比例缩小，在平面上，每次缩到原来的 77% 左右。 [18:32] 可行域如果不是空的，它的面积不会小于一个由输入数字的位数决定的下限，所以要不了太多次，就能找到可行点，或者断定最优解不存在。 [18:44] 一次次收紧，就能逼近最优解，总步数是输入长度的多项式。 [18:51] 这意味着，一个很多数学家都怀疑可能不存在高效算法的难题，其实有一个精妙的多项式算法。 [18:59] 线性规划在人类的统筹、调度、规划里极其普遍和重要，而现在这类问题有了一个通用的高效多项式算法。 [19:07] 这个结果也因此上了《纽约时报》头版。 [19:11] 历史上这样的事情发生过很多次，很多此前被人类长期认为不可能有高效解法的问题，最终发现存在一个天才的多项式算法，证明之前的研究者纯属自己不够聪明。 [19:26] 比如能不能只用 n 的多项式以内的步数判断一个 n 位数 x 是不是质数。 [19:33] 普通的方法是拿 2、3、4……一个个去试除，一直试到根号 x 为止，而 x 大约是 10 的 n 次方，根号 x 也有 10 的 n/2 次方，会随着位数 n 指数增加。 [19:46] 很长时间里，人们只有很快的概率性算法，却一直没有找到一个确定的、保证在 n 的多项式步数内判断一个 n 位数是不是质数的方法。 [19:58] 2002 年 8 月，印度理工学院坎普尔分校的阿格拉瓦尔，和他两个刚刚本科毕业的学生卡亚尔、萨克塞纳，发表了一篇论文，标题简单粗暴，PRIMES is in P，证明了判断质数存在高效多项式算法，属于 P。 [20:16] 再比如说计算两个 n 位数相乘，列竖式相乘需要计算 n 平方次乘法，如果不是专门学过，你可能很难想象这个问题的复杂度可以加速到 n 的 1.58 次方，甚至用快速傅里叶变换能做到 n log n。 [20:33] 所以，想要判断一个问题是不是真的很难、不存在多项式的快速算法，人类的感觉是靠不住的，因为可能只是我们很笨、没有想到好办法而已。 [20:44] 要断定等和划分问题不在 P 里，就必须证明所有可能的算法，包括还没有任何人想到的那些，都无法在多项式步数内完成。 [20:57] 一个人如何能证明所有无穷多个潜在的算法，甚至是自己都没有想到的那些，都无法在多项式时间内解决问题呢？ [21:08] 虽然给出问题通用且高效的解法很困难，但很多时候，验证一个具体的解答是不是正确答案却很容易。 [21:18] 1874 年，英国经济学家、逻辑学家威廉·斯坦利·杰文斯出版了一本讲科学方法的书叫做《科学原理》。 [21:27] 书中有一节，问读者能不能说出哪两个数相乘等于 8616460799，接着写道，我想，除了我自己，恐怕不会有别人知道了。 [21:39] 在他看来，这两个数都是很大的质数，要从乘积找回它们，只能拿质数一个接一个地去试除，一个熟练的计算员恐怕要花上好几个星期，而他把两个因数乘起来，只用了几分钟。 [21:54] 那个年代的 computer 不是机器，指的是以计算为职业的人。 [21:58] 这一节的标题叫"归纳是一种逆运算"。 [22:01] 杰文斯用乘法和因数分解作比，说明从原因推出结果容易，从结果倒推原因难。 [22:11] 1903 年，美国数学家莱默把它分解了出来，89681 乘以 96079。 [22:18] 你可以拿计算器检查一下，只需要一次乘法； [22:22] 可要是从 2 开始一个个试质数，得试 8687 个，才能碰到 89681。 [22:31] 虽然今天的电脑做完这八千多次试除，用不了一毫秒。 [22:34] 可这种不对称并没有消失，只要稍微把数字的位数弄得再大一点，计算乘积仍然比逐一尝试每个质因数要快速得多。 [22:44] 1977 年，麻省理工的三位研究者正是利用这个特性设计了著名的 RSA 加密算法。 [22:52] 两个大质数的乘积公开出去，谁都可以拿它加密； [22:56] 两个质数留在自己手里，只有知道它们的人才能解密。 [23:00] 今天在实际网络中使用的 RSA，乘积有 617 位。 [23:05] 而人类公开分解过的最大的乘积只有 270 位，时间就在 2026 年 9 月，当时动用了上千块显卡，算了大约 30 个显卡年。 [23:16] 但计算两个一百多位数字的乘积，你的手机一秒不到就能完成。 [23:21] 这种正确答案难以寻找、验证答案是否正确却很容易的问题随处可见。 [23:28] 有很多问题的结构就像解一个复杂的密码锁，在不知道密码的情况下找到密码非常困难，除了暴力尝试所有的 n 位密码没有什么好办法。 [23:38] 但验证密码对不对很简单，把密码拨到需要验证的数字上，按下开关看有没有打开就行了。 [23:46] 比如说，数独填起来要绞尽脑汁，但检查数独很简单，只要把每行、每列、每个九宫格都扫一遍看看 9 个数是不是各不相同就行了； [23:59] 把很多个数字分成总和相等的两堆要试上千种方案，但检查某一种分法是否相等，只要把两堆各加一遍，看看是不是刚好相等就行； [24:10] 扫雷也一样，根据数字找出地雷很困难，但给你一种埋雷方式，对着每个数字验证周围的地雷数量是不是的确等于这个数字却非常简单。 [24:23] 这种像老师改卷一样检查判断最终答案是否正确的流程，叫做检查程序。 [24:29] 有些问题，写解答程序很难，写检查程序却很容易。 [24:34] 为了刻画这种特性的问题，计算机科学家提出了NP问题。 [24:39] 要完全准确理解它的含义，我们还是得回来认识一下老朋友——图灵机。 [24:45] 图灵机有一条无限长的纸带，分成一个个格子，每格写一个符号； [24:50] 纸带上方有一个读写头，内部记着一个状态。 [24:54] 机器照着一张规则表工作，每条规则都写着，处在某个状态 q 下、读到某个符号的时候，写下什么，读写头再向左还是向右移一格，状态换成 q′。 [25:06] 机器每一步都查表执行，直到进入接受或者拒绝的状态，可以理解为这台机器判断问题有解或者无解。 [25:15] 我们今天写的任何程序，都能改写成一台图灵机。 [25:20] 用这个模型我们就能精确地定义 P 问题，存在一台图灵机和一个多项式 p，对于任何长度为 n 的输入，它最多走 p(n) 步就会停下来，并且给出正确的是或否。 [25:33] 那什么是 NP 呢？ [25:37] 在普通的图灵机里，状态和读到的符号一旦确定，下一步该做什么就只有一条规则，这叫确定性。 [25:46] 而有另一种神奇的图灵机，叫做非确定性图灵机，同一个状态读到同一个符号，规则表里却可以同时写着好几条规则，机器可能选择其中任何一条规则行动，然后继续。 [26:01] 只要存在一系列规则的选法，能让机器最终走进接受状态，就算机器接受了这个输入、找到了答案。 [26:11] 这种不确定正是 NP 中 N 的意思，nondeterministic。 [26:16] 好多人可能都误解 NP 的意思就是 not P，这就闹经典笑话了，P 怎么会等于不是 P 的东西呢？ [26:23] 拿等和划分这个问题来说，非确定性图灵机的程序流程会非常的妖，简直就是神秘的神灵。 [26:32] 第一段，从左到右扫过十个数，每扫到一个，就在两条规则里非确定性地选一条，在它下面写上 0 或者 1，代表这个数字属于左边那堆还是右边那堆，一共做十次选择。 [26:47] 第二段是普通的确定性计算，把标了左的数加起来，把标了右的数加起来，比较两个和，相等就返回找到答案。 [26:57] 容易理解，如果这些数字确实能分成总和相等的两堆，那么 1024 种选法里至少有一种能走到接受，按照定义，非确定性的图灵机就一定能找到这个答案。 [27:12] 你肯定会问了，我哪知道每一次非确定性的分支，这个图灵机到底猜了个啥？ [27:17] 哎，这就是 NP 最精髓的地方。 [27:20] 你可以想象它有一个神奇海螺，每一次选择都能完美地猜对； [27:26] 或者，你也可以想象它在每个岔路口分身，同时探索不同的分支，最后 1024 个分身同时去跑第二段答案检验，只要有一个找到答案就算成功。 [27:41] 第一段只要线性扫一遍，步数是 n，第二段只是普通的加法和比较总和，也是 n，所以整台机器的步数不超过 2n，当然是输入长度的多项式，因此等和划分问题属于 NP。 [27:54] 你可以从这个例子里看出，非确定性图灵机比确定性图灵机强大得多，简直就像开挂一样，未卜先知、却又在最后丝丝入扣。 [28:05] 一个问题有简单的检查程序，和它能被非确定图灵机在多项式时间内解决是一码事。 [28:13] 因为一旦有一个多项式时间的检查程序，只需要前面加上一段非确定性的开挂猜答案，整体就变成了一台非确定性图灵机，它在多项式时间内解决了问题。 [28:25] 所以 NP 问题也可以这么表述，当答案为是的时候，存在一份能在多项式步数内确认答案正确的凭据。 [28:35] 容易注意到，P 里的问题都在 NP 里，因为确定性的机器，本来就可以看成一台拥有超强的神奇海螺瞎猜能力，但从不使用的机器。 [28:46] 既然不用这种能力都能在多项式时间内用算法找到答案，那么有了强大的不确定性当然更加可以在多项式时间内完成，自然是 NP 的。 [28:58] 所以，P 是 NP 里面的一个子集。 [29:00] 那么这两个圈是不是同一个圈？ [29:05] 这就是 P 与 NP 问题：能快速检查答案是否正确的问题，是不是都能快速找到解答本身？ [29:14] 或者说，一个普通的、平庸的确定性图灵机，能不能有一套神秘的方法比肩神明，也能在多项式的时间内获得非确定性图灵机指数分身、开挂猜测的能力？ [29:29] 其实很早就有人问出了几乎一模一样的问题。 [29:32] 1956 年 3 月 20 日，一封信从普林斯顿寄出。 [29:36] 写信的人是库尔特·哥德尔，收信的人是约翰·冯·诺依曼，现代电子计算机体系结构的奠基人之一。 [29:41] 这时候的冯·诺依曼已经确诊癌症，坐上了轮椅，几周之后，就住进了华盛顿的沃尔特·里德医院。 [29:49] 在信的开头，哥德尔说，得知您生病，我感到万分难过； [29:53] 听说您现在感觉好些了，我想冒昧地写信，和您谈一个数学问题。 [29:58] 在这之前，人类已经两次撞上数学的边界。 [30:02] 1931 年，哥德尔自己证明，有些数学命题是真的，却没法在系统内证明； [30:08] 1936 年，图灵证明，有些问题没有任何算法能解决。 [30:13] 这封信进一步追问第三件事：在那些机器原则上能解决的问题里，有多少能被快速解决？ [30:22] 信里，哥德尔问，给一个数学命题和一个数字 n，让机器判断这个命题有没有长度为 n 的证明，最少需要多少步？ [30:31] 他把这个步数记作 φ(n)。 [30:33] 他写道，如果真有一台机器，φ(n) 只是 n 的常数倍，甚至是 n² 的常数倍，那么，尽管存在不可判定性，数学家在是非题上的思考工作，就可以完全交给机器。 [30:47] 而且哥德尔认为，φ(n) 增长得这么慢，完全是可能的。 [30:51] 只可惜，至今没有找到冯·诺依曼的回信。 [30:55] 1957 年 2 月 8 日，他在沃尔特·里德医院去世。 [30:59] 这封信夹在他的文件里，三十多年没有人注意到，直到 1988 年，人们才在美国国会图书馆收藏的冯·诺依曼文件里发现了它。 [31:09] 其实，这正是 P 与 NP 问题。 [31:12] 一份写得足够细的证明，检查它对不对是机械的，一行行核对每一步是否合乎规则就行，很快； [31:22] 但找到它，却要在天文数字般多的写法里搜寻。 [31:27] 这个命题有没有一份不超过一百万个符号的证明，就是一个 NP 问题。 [31:33] 麻烦在于，想要严谨地证明 NP 和 P 的关系，情况非常棘手。 [31:38] 要知道，NP 是一个无穷大的家族，等和划分、数独、分解质因数，还有无数今天还没人想到的问题。 [31:47] 要证明 P ≠ NP，该挑哪一个最难的下手证明不存在高效算法？ [31:55] 反过来，如果要证明 P = NP，难道我们要给无穷多个问题一个一个去找算法吗？ [32:08] 为了解决这个问题，理论计算机学科提出了一个极为精妙的概念，叫做“归约”，reduction。 [32:15] 常有知乎问题问，如果有一种能力，能保证考试一定及格，那会有多厉害？ [32:22] 我的回答是，你将成为历史上最无解的人肉神谕机。 [32:27] 想象一下，我可以出一张卷子，第一道大题是证明黎曼猜想，61 分，剩下的题加起来 39 分。 [32:35] 然后让你来考试，并实现系统赋予你的“绝对及格之力”。 [32:41] 你要是能及格，就一定做出了黎曼猜想； [32:45] 用同样的办法，任何难题都能塞进这张卷子，那么千禧年难题还剩下五个，咱出一张卷子，一道题 20 分，满分 100 你又一定会及格，那这一场考试结束你就能解决三个，佩雷尔曼和怀尔斯来了在你面前也是弟弟。 [33:04] 这种像黑客一样，利用某一套系统能力，撬动一个不可思议的结果的过程，就叫归约。 [33:12] 有了这种归约，我们就能明白“一定及格”这个技能有多强，或者说做到这一点有多难。 [33:22] 归约的妙处，就在于它能证明，两个看上去毫不相干的问题之间存在神奇的联系，并说明一个问题不会比另一个问题更容易。比如解数独和图染色。 [33:37] 数独大家都听说过，九行九列一共八十一个格子，有些格子已经填好了数字，要把剩下的格子填满，让每一行、每一列、每个九宫格里，1 到 9 都恰好出现一次。 [33:50] 而图染色问题是说，给你一张图，图中有一些点和连接各种边的线，染色板里有几种颜色，能不能给每个点涂上一种颜色，让有连线的两个点颜色都不相同。 [34:06] 一个是填数字的游戏，一个是给图涂颜色，乍一看没有任何关系。 [34:12] 但接下来我们就会用归约证明，染色这个问题是更难的，如果你能高效地解决它，那么就能直接用这个现成的解法轻松解决数独。 [34:24] 方法是这样的。 [34:25] 把八十一个格子各画成一个点，同一行、同一列或者同一个九宫格里的两个格子，就用一条线连起来，这样每个点都连着二十条线。 [34:37] 再把 1 到 9 这九个数字，看成九种颜色。 [34:41] 于是，把数独填满，就等于用九种颜色给这张图染色。 [34:47] 这背后的妙处在于，根据染色规则，有连边的两个点不能同色，而同一行的所有点之间都有连线，因此只要完成了染色的要求，这一行就自动两两不同色了。 [35:00] 同理，同一列和同一个九宫格里的点两两连线同时保证了每一列和每一个九宫格内颜色是不同的。 [35:08] 所以只要这个图能成功染色，把颜色翻译回数字，一定每一行每一列每个九宫格里的数字都是两两不同、刚好覆盖1到9的。 [35:23] 当然了，还有一些问题。 [35:25] 数独问题里，有些格子一开始就填好了数字，这是数独最重要的题面。 [35:31] 而染色问题里的点全都是空白的，没有预先涂好颜色这一说。 [35:37] 怎么在一个空白的图里，逼迫某些特定节点一定只能是某种颜色呢？ [35:42] 办法是在图的旁边另外加上九个点，当作调色盘。 [35:48] 这九个点两两相连，于是它们必须涂成九种不同的颜色，正好一种颜色代表一个数字。 [35:55] 我们可以给调色盘的九个点各标上一个数字。 [35:59] 如果数独问题里某个格子一开始就写着 5，就把它和调色盘里除了 5 号色以外的八个点都连起来，那么根据染色要求，它就被迫只能涂成 5 号色。 [36:18] 对所有数独里一开始给定数字的节点做这样的操作。 [36:23] 这样，一整道数独，连同题目给出的数字，就被原封不动地翻译成了一个纯粹的染色问题。 [36:31] 这张图能用九种颜色染好，当且仅当这道数独有解； [36:37] 染好之后，按颜色把数字读回去，就是数独的答案。 [36:42] 这就意味着，假如有人发明了一个能给任何图快速染色的算法，那么任何一道数独，都可以先翻译成一张图，交给这个算法染好色，再按颜色读回数字，数独也就跟着被快速解决了。 [36:59] 所以，给一张图染色这个问题是比解数独更难的，因为能解决染色就能轻松完成数独。 [37:09] 或者说，染色问题至少和数独一样难，绝不会比数独更容易。 [37:14] 把问题 A 的任何一道题，在多项式步数内翻译成问题 B 的一道题，并且答案保持不变，A有解当且仅当B有解。 [37:23] 这就叫作把 A 归约到 B。 [37:26] A 能归约到 B，就说明 B 的难度大于等于A。 [37:31] 顺着这个思路，计算机科学家问出了一个更大胆的问题。 [37:35] 在 NP 这个无穷大的家族里，有没有这样一个问题，家族里的每一个问题都能归约到它身上？ [37:43] 如果有，它的难度就大于等于所有的NP问题，至少和所有 NP 问题一样难。 [37:51] 它的威力也大得不可思议，只要给它找到一个多项式算法，等和划分、数独、分解质因数、染色，连同那些今天还没人想到的问题，就全都有了多项式算法。 [38:04] 既然所有NP问题都有了多项式算法，P 就等于 NP； [38:09] 反过来，只要证明它没有多项式算法，那我们就找到了一个确定没有多项式算法的NP问题例子，P 就不等于 NP。 [38:19] 所以，我们不需要研究无穷无尽的问题，只需要盯住这个最难的NP问题，看看到底有没有多项式算法，就能直接决定所有 NP 问题是不是都在 P 里。 [38:33] 这样的问题，叫作 NP 完全问题。 [38:39] 可是，这种问题真的存在吗？ [38:42] 无穷多个NP问题，包括那些还没有被人想到的问题，居然都能翻译成这个问题的某个具体例子，规模还不大，听上去几乎不可能做到。 [38:52] 然而，1971 年，人类找到了第一个这样的问题。 [38:57] 1970 年，在加州大学伯克利分校当了四年助理教授的斯蒂芬·库克，没能从数学系拿到终身教职，转去了多伦多大学。 [39:06] 第二年 5 月，他在俄亥俄州举行的计算理论年会上发表了一篇论文，题目叫《定理证明过程的复杂性》。 [39:15] 多年以后，伯克利的理查德·卡普回忆这件事时写道，计算机系没能说服数学系给库克终身教职，是他们永远的耻辱。 [39:23] 库克证明，有一个叫作可满足性的问题，satisfiability problem，简称 SAT，是所有 NP 问题都能归约过去的。 [39:35] 他的出发点就是非确定性图灵机。 [39:38] 一台图灵机运行的时候，每一步的全部信息，纸带上每一格写着什么、读写头停在哪一格、内部是什么状态，合起来叫一个格局，configuration。 [39:50] 这里方便起见，我们把读写头的状态也当成一个格子，写进它所在的格子相邻左边。 [39:57] 把第 0 步的格局写成第一行，第 1 步写成第二行，一直写到第 p(n) 步，就得到一张表格。 [40:04] 这个表格的行数就是运行的步数，又因为一步最多移动一格，所以列数也不会超过步数的多项式量级，整个表格的大小是多项式的。 [40:14] 所有NP问题都能归约到SAT问题的核心原因是，任何一个NP问题能最后变成接受状态，也就是有解，本质上就等于说存在这样一张由一行行格局组成的表格历史，它的第一行写着输入，最后一行出现接受状态，而中间每相邻的两行，都符合规则表的演化规则。 [40:38] 因此，任何一个问题能不能被非确定图灵机找到解答，等价于这中间大片的空白能不能被恰当的填入符号，使得整个表格是合法的，构成了这个图灵机一步步运行直到找到解答的过程。 [40:56] 其实，想要这个表格合法的要求也不算很难。 [41:00] 只关注相邻两行，绝大部分的格子应该和上一步保持一样。 [41:05] 因为图灵机每一步只改动读写头所在的那一格。 [41:10] 所以第 t + 1 行第 i 格写什么，只取决于第 t 行第 i − 1、i、i + 1 这三格。 [41:17] 要么根本没有看到读写头，那就直接复制上一行的同一个格子。 [41:23] 或者出现了读写头的状态，那么我们就要求局部的变化是符合非确定性图灵机规则的某一条的。 [41:31] 比如这里，就符合q1在看到0时，可以变成q3并右移一格。 [41:38] 所以，整张表格合不合法，就可以拆成许许多多个小检查，每个只看上下两行里一个两行三列的小窗口，看它是不是规则表允许的样子。 [41:50] 每一个小窗口里，只需要满足某一条图灵机规则就可以，所以是或的关系。 [41:56] 而所有的窗口都要同时满足检查，所以是且的关系。 [42:01] 最终，整个表有没有一种合理的填法，就取决于我们能不能填入一系列的0和1，能让一个巨大的表达式成立。 [42:10] 这个表达式需要一系列局部都成立，每个局部成立的条件都能整理成几条从句，而从句成立只需要一系列规则里有一个满足就行，所以里面都是或的关系。 [42:23] 没错，这个问题就是大名鼎鼎的SAT问题。 [42:26] 需要填入的格子和整个表达式的长度都是 n 的多项式，把它们写出来也只要多项式步数。 [42:33] 我们前面说过，任何 NP 问题都有一台多项式时间的非确定机器，也就是先猜答案再检验的过程，所以任何 NP 问题是否有解都能这样归约到画一张表格，进而变成一个布尔表达式能不能为真的SAT问题。 [42:52] 一个确定性图灵机从上往下把表格一行行填出来很容易，只需要让机器正着跑完就行； [43:00] 而只知道最后一行要出现接受和初始状况，要倒着推出有多种转移规则的中间空白里该写下什么，却非常困难。 [43:13] 从这个角度来说，前面说的乘法和分解也是一样的道理。 [43:18] 正着算乘积，也就如同图灵机一样从上到下一行行算到结束。 [43:24] 而根据乘积分解，就相当于在竖式里把最后一行固定成 8616460799 ，再往回推一开始应该填什么，这就困难得多了。 [43:40] 库克还证明，这些要求总能改写成每个从句最多涉及三个开关的样子，这个版本叫 3-SAT。 [43:49] 不妨把它想成四个开关 A、B、C、D 和四盏灯，每盏灯下面挂一条要求，要求里至少有一项成立，灯就亮。 [43:58] 比如第 1 条是A 开或 B 开或 C 关； [44:03] 第 2 条，A 关或 B 开或 D 开，然后问怎么拨开关才能让所有灯全都亮。 [44:13] 之所以让每个从句只有3个，是为了方便其他问题能归约到它。 [44:20] 一个更容易理解3-SAT问题的比喻是，想象你开一家咖啡馆，要决定各种具体的因素，比如灯是亮还是暗、有没有音乐、过不过夜等等。 [44:29] 每个都是一个需要决定的变量，而每个顾客会提出针对某三个变量的要求，满足一个就行，比如要有音乐、或者能过夜、或者有拿铁之类的，客人的要求就是从句。 [44:42] 3-SAT就是在问，是否有一种对咖啡馆各种变量的设计方式，能够让所有的从句都成立，也就是让所有顾客一个不差的全都满意。 [44:55] 容易注意到，SAT 本身也属于 NP，给出一种开关的拨法，逐条检查每条从句是否成立就行。 [45:04] 所以它正是前面要找的那种问题，自己是NP的，但所有NP问题都能翻译成它。 [45:11] 这就是人类发现的第一个 NP 完全问题，是最难的NP问题。 [45:16] 从这一刻起，无穷多个问题，被收拢到了一个问题上。 [45:22] 几乎同时，在莫斯科，柯尔莫哥洛夫的学生列昂尼德·列文独立得到了同样的结论。 [45:28] 他的博士论文得到了导师和答辩委员会的认可，学位却因为政治原因被当局拒绝授予。 [45:36] 苏联的研究者把这类问题叫作 перебор，意思是穷举，挨个去试； [45:42] 列文那篇《通用的穷举问题》1973 年才发表，正文只有两页。 [45:47] 他后来说，自己推迟了发表，是想把另一个问题也放进去，给出一个函数的全部取值，找出能算出它的最小电路。他没能做到。 [45:57] 今天，这个定理被称为库克–列文定理。 [46:00] 如果说，一个SAT问题就能代表所有NP问题已经十分让人惊讶，那么接下来发生的事情则更加不可思议。 [46:10] 那就是，并不只有SAT这一个问题享有这样崇高的地位，许多看起来非常简单、像游戏一样的问题，居然也全都是NP完全的。 [46:21] 第二年，1972 年的 3 月，在纽约州 IBM 的研究中心，卡普在一次研讨会上报告了 21 个NP完全问题，五花八门。 [46:32] 比如，一张地图上有许多城市和道路，能不能找到一条路线，把每座城市恰好经过一次，最后回到起点，这个问题是 NP 完全的。 [46:42] 一群人里谁和谁认识都已经知道，能不能从中找出 k 个人，彼此两两都认识、或者两两都不认识，这个问题是 NP 完全的。 [46:53] 一台机器要处理一批任务，每个任务有自己的耗时、期限和误期罚款，能不能排出一个顺序，让总罚款不超过某个数，这个问题是 NP 完全的。 [47:05] 一个背包能装的重量是固定的，一堆物品轻重不一，能不能挑出一些，恰好把背包装满，这个问题是 NP 完全的。 [47:14] 要用电线把几座指定的城市连起来，中途可以经过别的城市，能不能让电线的总长不超过某个数，这个问题也是 NP 完全的。 [47:24] 顶点覆盖、集合覆盖、恰好覆盖、团覆盖、三维匹配、最大割、0-1 整数规划……二十一个问题，全都是 NP 完全的。 [47:35] 没想到吧！ [47:36] 那些看起来像游戏一样的问题，其实底层是极为困难的。 [47:40] 它们和SAT问题享有同样的地位，换句话说，如果你能高效解决把一个图染色的问题，或者这21个问题中的任何一个，你也就能多项式时间内高效解决所有的NP问题。这怎么可能？ [47:58] 染色问题为什么也有这种不可思议的难度？怎么证明的？ [48:02] 其实原理和之前一样，还是归约。 [48:05] 既然我们已经有了一个最难的无敌NP完全问题3-SAT，那么只需要证明，任何3-SAT问题都进一步翻译成某个具体的染色问题，其节点数量不超过变量和从句个数的多项式，通过巧妙的节点设置让这张图能够染色精确等价于原来的布尔表达式能够取值为真。 [48:29] 那么任何一个复杂的NP问题，都能翻译成一个等价的3-SAT问题，再进一步翻译成一个等价的染色问题，你能对任何图染色，就能解决任何NP问题，于是就成功证明了染色问题也是NP完全的。 [48:46] 怎么翻译呢？ [49:06] 我们将规定只用三种颜色，并且还是一样，先用一个三角形构建一个染色盘，这三种颜色分别命名为T、F、B，分别对应于真、假和辅助颜色。 [49:21] 对于每一个变量xi，我们构造节点xi和not xi，它俩和B连成三角形。 [49:28] 这样根据连边不同色的规定，只可能xi和not xi一个T一个F，对这两个节点的染色就相当于对变量赋值。 [49:38] 接着我们来设计各种辅助节点。 [49:41] 对于每一个从句l1 or l2 or l3，我们都引入5个辅助节点，长成这个样子。 [49:48] (l1-a, l2-b, abc三角, c-d, l3-e, deT三角) 你可能会问，这何意味？ [49:50] 答案是，这样设计的目的是为了确保一个从句所涉及的l1, l2，l3三个变量中，想要成功三染色，必定有至少一个是T。 [50:02] 因为如果三个变量都不成立、是F，那么e只能是B，那么d只能是F。 [50:12] 可是问题就出现了，abc形成了三角形，它们颜色两两不同，其中必然有一个是F，可是现在三个节点都和某个颜色是F的节点相连，都不能是F，所以矛盾了。 [50:29] 因此这5个辅助节点的设计非常巧妙地迫使所有从句对应的3个节点里至少要有一个是T。 [50:40] 就这样，对每一个从句整这么五个点出来。 [50:43] 最后把一整个图交给染色机器，问它：说！ [50:47] 这个图能不能用三种颜色染色？怎么染。 [50:50] 一旦染色成功，你看看一开始那些变量的赋值情况，就得到了3-SAT问题的解。 [50:59] 你肯定要问了，这5个辅助节点逼迫每个从句都要成立的操作是怎么想出来的？答案是科学家注意到的。 [51:07] 卡普一口气注意到了SAT问题可以一路巧妙地翻译成21个不同的问题，从而证明了它们都是NP完全的。 [51:16] 我们姚班算法设计的考试就成天找一个奇奇怪怪的问题，让我们设计这套归约的翻译过程，证明它是NP完全的。 [51:26] 到1979 年，算法设计的教科书附录里已经收录了约 300 个 NP 完全问题，到了今天，人类已经发现了好几千个NP完全问题，遍布流程统筹、芯片设计、生物、经济学、甚至是投票机制设计。 [51:42] 五十多年来，每个领域都有人想给自己的那个问题找到快速算法，但没有一个人成功。 [51:49] 复杂度理论告诉人类，因为它们其实是同一个问题，这几千次失败，都是在同一个问题上的失败。 [51:57] 它们困难的核心到底在哪里呢？ [52:01] SAT给了一个统一的视角和诠释。 [52:04] 因为这些问题都由许多局部的规则组成，每条规则只管某几样条件之一需要成立，可规则之间环环相扣、极为复杂地纠缠耦合在一起，不同局部的规则之间互相矛盾，要让所有规则同时成立，就得在整体上协调。 [52:25] 一旦一个问题有了这种“众口难调”的底层特性，立刻就会变得极为棘手，拥有了NP完全的潜质。 [52:34] 而归约证明的过程，就在于怎么发挥这个问题的这种潜质，将任何一个3-SAT问题落实在这种特定问题的具体例子上。 [52:45] 卡普之后，NP 完全问题出现在越来越意想不到的地方。 [52:50] 比如，2000 年，英国伯明翰大学的数学家理查德·凯伊发表了一篇论文，题目就叫《扫雷是 NP 完全的》。 [52:59] 扫雷问题大家都玩过，给出一个部分翻开的扫雷局面，判断有没有埋雷的方式，能让每一个翻开的数字刚好对应于它周围八个格子里有几颗雷。 [53:11] 同一年，千禧年大奖刚刚公布，数学科普作家伊恩·斯图尔特就在《科学美国人》上写了一篇专栏，标题叫《百万美元扫雷》。 [53:21] 要证明判断扫雷局面是否自洽是 NP 完全的，只需要说明，任何一张 3-SAT 要求的清单都能翻译成一个扫雷局面，并且SAT能被满足，当且仅当这个局面存在一种对应的埋雷方式。 [53:40] 整个设计的起点起源于一个扫雷里经典的名场面，那就是像这样，所有地方都完事了，只剩最后两个格子二选一，哪一个有雷都满足，但没有任何其他的信息能帮助判断，只能生死二选一。 [53:58] 在你点下去之前，这颗雷像薛定谔的猫一样，在左边和在右边两种可能同时成立。 [54:05] 数学家就想到利用这一点，正好可以拿来当一个0和1的开关。 [54:10] 如果x有雷，这根导线传递的就是高电平1，如果是x'有雷，那么这根导线传递的就是低电平0。 [54:19] 凯伊接下来展示了巧妙的设计，可以让一个局部二选一的量子叠加态不断传递，让好多个量子态纠缠在一起，形成导线一样的结构。 [54:31] 具体构造是这样的，中间一行按 x、x′、1 的顺序一直重复，x 和 x′ 是一对未翻开的格子，后面跟着一个翻开的 1； [54:41] 紧挨着它的上下两行全是翻开的 1，最外面两行是翻开的 0。 [54:47] 上下的 1 保证每一对 x、x′ 里恰好有一颗雷，这就是一个二选一； [54:54] 夹在两对之间的那个 1，又保证前一对的 x′ 和后一对的 x 里恰好有一颗雷。 [55:01] 所以只要其中任何一对坍缩，比如 x′ 有雷，下一对的 x 就不能有雷，只能 x′ 有雷，再下一对也一样。 [55:12] 这样，一瞬间整根导线到底是 x 有雷还是 x′ 有雷就被确定了。 [55:18] 整根导线上的叠加态被穿在一起。 [55:21] 凯伊还通过设计，让导线可以拐弯也可以分岔出好几个接头甚至还能让两根导线互不影响地交叉 [55:33] 接着，凯伊还为这种逻辑电路设计了一整套逻辑门，也就是说，通过设计周围数字的结构，让导线里的量子态取反； [55:44] 通过这样的扫雷顺序，你就会发现，经过这个结构后，导线内部从左边有雷变成右边有雷，这就是非门。 [55:52] 有了非门，凯伊还造出了与门，输出量子态是两者的and； [55:57] 有了与门和非门，或门也就有了，输出是两根导线结果的or [56:04] 有了这套零件，就可以把任何一张 3-SAT 要求清单一路编译成扫雷局面。 [56:11] 而且这套过程可能是所有归约里含义最直观的：真的把3-SAT里对应的布尔电路在扫雷的板子上搭建出来。 [56:22] 每个开关变量是一根输入线，每条从句要求对应于两次或门，它会接入每个变量或者变量经过非门的取反，比如说这个x1 or x2 or not x4就会这样。 [56:36] 如此，一个或门的输出就是这个从句是否满足的结果； [56:41] 接着把所有从句的导线全部用且门接在一起，最后接入一个强迫最后结果必须是真的终端。 [56:50] 好了，构造完成，请您扫雷。 [56:54] 你会发现，这样拼出来的扫雷局面，要找到一个和所有数字都对得上的埋雷方式，本质上要求你给出每个开关变量的具体取值，使得在每个逻辑门和电线位置都是自洽的。 [57:11] 所以，如果真的存在一个完美高效的扫雷专家，它在这种具体问题里略施拳脚，就能轻松解决SAT问题，所以扫雷不比SAT问题容易，也就至少和所有NP问题一样难。 [57:26] 扫雷本身是NP问题则更容易了，给出一种具体埋雷方式以后，逐个核对每个数字是不是满足很快，所以扫雷也是一个 NP 完全问题。 [57:48] 在那之后，人类在各种千奇百怪的游戏里都构造出了这样的导线和逻辑门，数独、俄罗斯方块、超级马里奥、糖果传奇……从而证明这些游戏底层都蕴含着人类最困难计算问题的复杂性。 [58:04] 这里需要进一步纠正一个常见的误会，一个问题是NP完全的，就意味着人类拿它束手无策，这个问题我们只能干瞪眼、暴力枚举。 [58:15] 事实上，我看到过很多小游戏，它们底层都是NP完全问题，就是确保这些问题没有高效系统的方法、看起来又很简单有趣，从而最大程度调动用户的兴趣、消耗时间、并在玩家卡壳的时候让他们点击广告。 [58:34] 有些甚至比 NP 问题还难，是 PSPACE 完全的。 [58:42] 可大家照样玩得开开心心，一关关都解得出来。 [58:46] 这是因为，就算 P ≠ NP，NP 完全问题的很多具体例子在现实里也常常能有比较高效的解法，或者是启发式算法。 [58:56] 因为NP 完全说的是最坏的情况，没有一个算法能在所有题目上都快； [59:02] 可现实里的题目大多有结构。 [59:04] 比如说，找到一条总路费成本最低的回路，把每个点都过恰好一遍，这叫旅行商问题，是 NP 完全的，可 2025 年，人们算出了韩国八万多家酒吧之间最短的巡回路线，还证明了它确实最短，因为这些酒吧散落在真实的地图上，距离有很好的几何结构，求解器能剪掉绝大多数走法； [59:27] 芯片公司每天都在用 SAT 求解器，处理带着上百万个开关变量的复杂逻辑要求清单。 [59:35] 这也是因为这些变量之间的纠缠并没有达到理论上最复杂的程度，所以实际可解性很强。 [59:42] 如果放松“每个从句差一个都不行”的要求，转而追求满足尽可能多的从句，那么纯随机的方法更是能在期望意义下满足7/8的从句。 [59:54] 可是对于能全部满足的式子，这个87.5%的比例也是极限了，如果有算法能比它再多哪怕一点点，比如确保满足超过0.8750001的从句，那么NP就会等于P。 [60:08] 这背后的原理非常复杂，我们就不在这一期视频里展开了。 [60:14] 假如 P 真的等于 NP，而且那个算法够快，世界会变得很不一样。 [60:21] 计算机科学家斯科特·阿伦森写过一段话，大意是，如果 P 等于 NP，那么能欣赏交响乐的人都会立刻成为莫扎特，能跟上一步步论证的人都会成为高斯。 [60:33] 在那个世界里，老手和新手没有区别。 [60:36] 我们说一个人经验丰富、直觉好、有品味，说的其实是他能在指数多的可能性里，比别人更快地找到对的那一条路。 [60:45] 要是找和验一样容易，只要你认得出好答案，你就找得到它，经验和直觉也就不再值钱。 [60:52] 与此同时，如果 P 等于 NP，密码学也会随之消失。 [60:58] 网上几乎所有的加密，都建立在正着算容易、倒着推难的过程上，比如两个质数相乘容易、分解困难，椭圆曲线、格密码也是同样的道理，2024 年刚刚定下的抗量子标准也不例外。 [61:13] 如果任何正着算很快的过程都能被快速倒推，这些密码也就全都不可靠，可以被高效破解。 [61:21] 正因此，大多数研究者相信是 P 不等于 NP。 [61:25] 计算机科学家加萨奇做过三次调查，认为 P ≠ NP 的人从 2002 年的 61%，涨到 2012 年的 83%，再到 2019 年的 88%。 [61:36] 也有人押另一边，比如写过《计算机程序设计艺术》的高德纳就说，他渐渐相信 P = NP，只不过那个多项式的次数可能大得无法想象，证明也多半给不出具体的算法。 [61:51] 为了 P 与 NP，人们交过很多份答卷。 [61:54] 荷兰数学家沃金格维护过一个网页，收录了 116 份宣称解决了这个问题的论文，61 份说等于，49 份说不等于，但最后没有一份站得住脚，全都有各种各样的问题。 [62:07] 2010 年 8 月，惠普实验室的研究员德奥拉利卡尔把一份 P ≠ NP 的证明发给同行，几天之内，世界各地的专家在博客上逐行检查，阿伦森公开表示，如果这份证明拿到克雷奖，他自掏 20 万美元追加奖金。 [62:24] 结果一周左右，证明里的漏洞就浮出了水面，还是一场炸胡。 [62:28] 为什么证明这么难？ [62:31] 回想之前的视频我们如何证明尺规作图无法做出三次根号2，数学里想要证明一类方法不可能达成某一个目标，需要对所有这样的方法进行最精炼的本质概括，比如尺规作图本质上都是四则运算和开根号。 [62:49] 再基于这样的本质总结出它能力的边界，并证明目标在边界之外。 [62:56] 可是，P不等于NP这个问题本身带有一种悖论式的困难性。 [63:01] 因为某种意义上，人类能够想到的算法和智慧的边界都是P的，也就是按部就班、按照某种确定的规律法则执行比较少的多项式次数。 [63:13] 可我们居然要证明所有我们未曾想到的无穷多的算法，都不可能高效解决某个问题。 [63:20] 这就好比一个小孩说，我只会数数，但我能证明人类的ZFC公理体系不可能证明黎曼猜想。 [63:28] 人类目前对所有多项式算法的建模是逻辑电路。 [63:32] 一个能在多项式步数内解决的问题，都能用多项式个逻辑门的电路算出来。 [63:37] 最底下一排是输入，每个输入是 0 或 1。 [63:41] 往上是一层层逻辑门，比如与或非门。 [63:44] 门和门之间用导线连起来，最顶上那根线吐出答案。 [63:50] 一个电路有多复杂，取决于它用了多少个门。 [63:53] 计算机运行一个算法，每一步不过是根据内存上一刻的状态算出下一刻的状态，而这一步本身就能用一小撮门搭出来。 [64:03] 把运行过程一步一步展开、摞起来，就得到一个电路。 [64:07] 算法跑多少步，电路的门数大致是步数的平方。 [64:11] 所以，凡是能在多项式步数内解决的问题，都能用多项式个门的电路解决。 [64:18] 反过来，只要证明某个 NP 问题需要的门多到超过任何多项式，就证明了 P ≠ NP。 [64:26] 这就是目前P和NP问题研究的前沿领域，叫电路复杂度。 [64:33] 按理说，复杂的电路函数应该多的是。 [64:36] 1949 年，香农做过一个数数的论证。 [64:39] n 个输入的布尔函数，就是给每种输入组合指定一个 0 或 1，一共有 2 的 2ⁿ 次方种，是双重指数。 [64:49] 可门的数量有限的电路，能拼出来的花样远远没有这么多。 [64:54] 所以绝大多数函数都需要大约 2ⁿ/n 个门，是指数级的。 [65:00] 随手抓一个函数，它几乎一定是难的。 [65:06] 可直到今天，对一个具体的函数，人们在一般电路上能证明的最好下界只有大约 3.1n 个门。 [65:14] 这个纪录是 2022 年两位清华姚班的本科生李佳图和杨天祺创下的，之前的纪录是 3.01n 左右。 [65:22] 然而即便如此，从 3.1n 到超过任何多项式，中间隔着遥不可及的鸿沟。 [65:30] 这些年里，人们对NP完全问题，或者更具体的说3-SAT问题有多难，还提出过一个比 P ≠ NP 更具体的猜想，叫指数时间假设。 [65:41] 简单来说，这个假设不仅认为NP完全问题不存在多项式算法，还给这个算法需要的步数一个具体的下界，那就是至少要指数步的时间。 [65:52] 无论是判断一个布尔表达式是否有结果为真的变量赋值，还是我们一开始所讨论的等和划分问题，本质上，我们都逃不开指数级别的尝试。 [66:02] 不一定真要把所有可能一一试遍，也许是 1.3 的 n 次方、1.1 的 n 次方，但总归是某个 c 的 n 次方，这堵墙躲不开。 [66:13] 3-SAT 这样的 NP 完全问题必须要指数的时间才能完成，这就是指数时间假设，Exponential Time Hypothesis。 [66:28] 人类科学家几乎都相信它是真的，如果一个密码锁不同的密码之间没有联系，那我们最坏情况下不是肯定要一一尝试所有的指数量级的密码才行吗？ [66:40] 然而，2026 年 10 月 26 日，OpenAI 在公开的数学成果记录里挂出了一份手稿，标题就是《指数时间假设是错的》。 [66:49] 这份手稿声称，它找到了一个确定性的算法，可以在比指数更快的时间里，精确数出任何一个具体3-SAT问题有多少个输入使得表达式为真。 [67:02] 不过快的程度不大，也就是从2^n变成了2^{n/sqrt{log n}}，指数上多除以了一个根号log n，但在量级上，它已经比任何 c 的 n 次方都快。 [67:16] 截至目前，证明还没有经过同行审查，一个由因帕利亚佐、帕图里和威廉姆斯牵头的独立小组正在审查。 [67:29] 如果它成立，几十年来许多以这个假设为前提、断言"某某问题不可能更快"的结论，都要重新审视，几百篇以这个假设成立为基础的论文，地基前提完全垮塌，所有结论全部需要重新审视。 [67:47] 这意味着，当n趋向于无穷大时，有一种神秘的方法可以通过一次变量开关的设置，系统性地测试一大堆不同变量组合的可行性，这对于一直相信指数时间假设为真的理论计算机科学家们来说是完全不可思议的。 [68:06] 虽然这个算法不是多项式的，这依然不能证明NP等于P，但是NP问题的难度已经发生了松动，指数复杂度这堵墙已经被打开，接下来会发生什么，我们不得而知。 [68:22] 数学证明不了，大自然会不会替我们算出来？ [68:25] 有一种说法流传了很久，肥皂膜总会收缩到面积最小，所以把它张在几根钉子之间，它就能找出连接这些钉子的最短网络，而这是一个 NP 难的问题，叫斯坦纳树问题。 [68:39] 2005 年，阿伦森真的做了这个实验。 [68:42] 他用两块玻璃板夹住几根铜钉，浸进肥皂水再提起来。 [68:47] 三四根钉子的时候，肥皂膜通常能找到最短的网络，但也不总是； [68:53] 钉子一多，它常常停在更长的形状上，有时还会出现三条膜围成的小三角形，这在最短的网络里根本不可能出现，同样的装置再浸一次，得到的形状又不一样。 [69:07] 肥皂膜只会停在附近最短的形状上，它也会卡住。 [69:13] 计算机科学家阿伦森在他 2013 年出版的一本书里提出，也许应该把"NP 完全问题在物理世界里没有高效的解法"当作一条物理原理来看待，就像热力学第二定律一样，永动机造不出来。 [69:28] 它没有被证明，可到今天为止，不管是电脑、肥皂膜，还是我们正在建造的量子计算机，都没有让它打破这个规则。 [69:36] 如果这条规律成立，我们住的就是一个找答案比验答案难得多的宇宙。 [69:43] 正是因为难，秘密才守得住，一个好的想法才珍贵，一个人的经验、直觉和洞见，才有它的分量。 [69:52] 如果NP真的等于P，而且这个算法还非常高效，不是n的20000次方这种算法。 [69:57] 那这个世界将会无比的令人兴奋，但也会恐怖至极。 [70:02] 以上就是NP和P问题的科普，作为本科专业就是理论计算机的姚班毕业生，这期视频倾注了我大量的心血。 [70:10] 如果你觉得这期内容有意思，欢迎点赞支持一下。 [70:13] 之后我还会做更多这样的科普，一定记得关注我。 [70:17] 漫士沉思录，学海引路不辛苦，我们下期再会。（列参考资料表）