# 理查德·卡普：算法与计算复杂性 > 图灵奖得主回顾算法研究生涯，谈 NP 完全性、随机化算法与计算复杂性理论的意义。 - 原标题：#111 – Richard Karp: Algorithms and Computational Complexity - 期数：第 111 期 - 发布日期：2020-07-26 - 嘉宾 / 主题：理查德·卡普：算法与复杂性 - 网页版：https://lexfridman-cn.pages.dev/ep/richard-karp/ - 官方页面：https://lexfridman.com/richard-karp/ - 精读字数：约 20117 字（阅读约 45 分钟） > 本文为 lex.qiaomu.ai 基于原始访谈的 AI 改写中文精读，非官方翻译；引用请注明出处并链接网页版。 1955 年，一个哈佛博士生加入了 Howard Aiken（霍华德·艾肯）的计算实验室。实验室里有一台叫 Mark IV 的机器，占满整个房间，人可以走进去，两侧是一排排继电器。 机器经常出故障，原因有时候是虫子真的飞进去，落在了开关上。英文里 bug 这个词后来变成了“程序错误”，但在那个年代，它是字面意义上的虫子。 这个博士生叫理查德·卡普（Richard Karp）。三十年后他拿了图灵奖，理由是“对算法理论的研究”，其中包括埃德蒙兹-卡普算法、霍普克拉夫特-卡普算法，以及一篇 1971 年的论文。那篇论文里，他证明了 21 个看起来毫不相干的组合问题，其实是同一个问题的不同马甲。 这场访谈里，卡普把这七十年的思考压缩成了一次聊天。从 13 岁被一个几何证明震住，到怀疑计算机永远追不上六个月大的婴儿。 ## 一个证明，能把一个孩子钉在原地 卡普 13 岁第一次接触平面几何，被证明的力量和形式之美震住了。 他讲了迈克尔·拉宾（Michael Rabin）的一个故事。拉宾小时候因为调皮被赶出教室，在走廊里晃荡，碰到两个高年级学生在研究一个问题：两个不相交的圆，它们之间的最短距离是多少。 拉宾想了一会儿说：连心线。把两个圆心连起来，夹在两圆之间的那一段就是最短的。因为任何连接两圆的线段，向两边各延长一个半径，就得到一条连接两圆心的三段折线，它不可能比直线更短。 卡普说，他听完这个证明，和拉宾一样觉得这就是优雅。纯推理，能得出一个无可争辩的结论。 > 你可以用纯推理确立一个几何事实，而且无可争辩。（理查德·卡普） 三角形内角和 180 度也是这样。过一个顶点作对边的平行线，利用内错角相等，三个角拼成一个平角。卡普说这件事的惊人之处不在难，恰恰在它太容易了。容易，却又如此有说服力。 他还说了一句挺诚实的话：自己的三维视觉很差，想象不出三维曲面和超平面。所以后来做线性规划，他靠的是代数性质，几何直觉帮不上忙。“在脑子里看到一个多面体的最高点”这件事，对他而言是动机，还谈不上工具。 ## 算法在脑子里长什么样 Lex 问他，设计算法的时候脑子里在发生什么。 卡普的描述很朴素：算法通常是一个内层循环的重复，所以他能“看到”当前解到目标解的距离在迭代中不断缩小，直到最后落到精确解上。每一步都要保证在靠近，还要保证一定会收敛。 他拿旅行商问题举例。有一个目标函数需要最小化，看着它一步步逼近最优值，这件事本身就很迷人。 这里有一处区分值得停下来。设计算法包含两件事：直觉上猜到解长什么样，以及严格证明它一定会收敛、一定跑在某个复杂度内。哪一部分更难，魔法发生在哪里？ 卡普的回答是：魔法就在于那个差值单调下降，你能眼看着各种指标一路改善，直到撞上最优解。 他接着提到高德纳（Don Knuth）的一个说法：有一类人，能从审视计算过程的结构中获得巨大的审美愉悦。高德纳管这种人叫 geek。 卡普记得自己意识到“我就是这种人”的那个瞬间，是有人给他看匈牙利算法解分配问题的时候。 ## 把一行数字减掉一个常数，最优解不变 分配问题：n 个男孩，n 个女孩，给定每个男孩和每个女孩配对的成本，求一种一一对应，把总成本压到最低。 关键观察只有一句话：**从矩阵的任意一行或任意一列减去同一个常数，最优排列不变。**因为某一行的所有元素都减了同样的量，每个完整解的代价都减了同样的量，比较关系没变。 于是算法就变成了：从非负矩阵出发，不断地从行或列减去常数，始终保持所有元素非负，直到矩阵里出现一个全零的完整排列。那个排列就是最优解。 实际做的时候要稍微绕一点。只减不加会把某些零变成负数，所以每一步是从一些行和列减去常数，再给另一些行和列加回去，让已有的零保持不变。整体效果是总成本下降。 怎么找这些行列？靠计算矩阵里元素之间的一种最短路。听起来绕，做起来是多项式时间的。 卡普说，如果他有动手能力，大概会喜欢做木工，把一块木头削成漂亮、有序的东西。迭代算法那种有条不紊的性质，给他的是同一种快感。 这种审美不是后天培养的。他小时候靠心算四位数乘法自娱自乐，还靠从 1 开始不断翻倍、直到记不住为止来催眠。在波士顿郊外的海滩度假村打暑期工，他的岗位是招揽顾客，对着麦克风喊“来吧来吧，五分钱玩一局”。同事是一群对学术毫无兴趣的小混混，他靠心算四位数乘法把他们镇住了。 ## 1971 年，21 个问题被绑上了同一条船 1971 年，斯蒂芬·库克（Stephen Cook）发表了一篇论文，证明了一件事：**命题逻辑的可满足性问题（SAT），和 NP 类里的任何问题一样难。** SAT 的表述简单到可以在中学课堂上讲。给你一堆由“与、或、非”构成的逻辑表达式，问是否存在一组变量赋值，让整个表达式为真。 比如把 (A 或 B)、(A 或非 B)、(非 A 或 B)、(非 A 或非 B) 这四个子句全部“与”起来，你会发现无论 A 和 B 怎么取值，总有一个子句是假的。这个公式不可满足。 库克证明的是：NP 里的每一个问题，都能重写成 SAT 的一个实例。 他用的工具是图灵机。图灵机极简：一条纸带，一个读写头，一张有限的状态转移表。任何现实计算机上的算法，都能翻译成图灵机上的等价程序。反过来，任何非确定性多项式时间的算法，都能描述成一串“读到某个符号、处于某个状态、写下新符号、移动到新状态”的指令，而这串指令本身可以用逻辑公式写出来。 卡普看到这篇论文时意识到：**SAT 是一个通用的组合问题。**所有解容易验证的问题，都能翻译成它。 > 看到库克的证明，你会意识到 SAT 是所有 NP 问题的通用形式。而我凭之前解题的经验知道，还有很多别的问题也带着这种通用结构。（理查德·卡普） 于是他开始反方向找归约：从 SAT 出发，能不能翻译到别的问题上？ 第一个是整数规划。跟线性规划长得一样，一组线性不等式，但变量必须是整数，甚至是 0 或 1。这个额外约束让问题难得多。把 SAT 写成整数规划并不难：每个变量一个 0/1 变量，每个子句一条不等式。 第二个是团问题。图里有没有一个大小为 k 的完全子图，其中任意两个顶点都相邻。 这个归约值得细看，因为它展示了这类翻译是怎么工作的。 把 SAT 公式写成若干子句的合取，每个子句是一串变量或变量否定的析取。要满足整个公式，每个子句里至少要挑一个“真”的项，而且不能同时挑中同一个变量的正版本和负版本。 现在造一张图：顶点是每个子句里的每个项，也就是每一次变量出现。边有两类。第一类，同一个子句内的任意两个顶点之间连边，因为你只能从这个子句里挑一个。第二类，如果两个顶点是同一个变量的正负两次出现，也连边，因为你不能让它既真又假。 那么“挑一组互不相邻的顶点，每个子句恰好挑一个”，对应的就是独立集问题。而独立集的大小等于子句数，就等价于原公式可满足。 Lex 在访谈里说他很难相信这件事是真的：一张图和一条逻辑公式，居然能这样对应起来。 > 我也很难相信。但它们就是有同样的表达力。你可以把其中任何一个翻译成另一个的语言。（理查德·卡普） 这里有个细微但重要的点。表达力相同，不等于计算复杂度相同。两个问题可以互相翻译，但翻译本身可能带来规模爆炸，所以它们的难度未必一样。卡普说得很清楚：它们等价的地方在于“谁能表达谁”，不在于“谁算得快”。 能够确定的是：**这些问题要么全都能在多项式时间内求解，要么全都不能。** 1971 年那篇论文里，卡普挑了 21 个基本的组合问题，覆盖打包、覆盖、匹配这些常见类型，证明它们全都和 SAT 等价。这等于把战书扔在了地上：这样的问题肯定还有一大堆。 ## NP 完全和 NP 难，差别在一个技术细节 卡普说这俩的区别是个“小小的技术性问题”，但值得讲清楚。 决策问题的答案是是或否。比如“图里有没有大小为 15 的团”。优化问题的答案是数值，比如“最大的团有多大”。 两边的难度是对应的。决策版本里最难的那批叫 NP 完全，优化版本里对应的最难的那批叫 NP 难。核心的等价链条一样，只是问题的表述形式不同。 那么，如果 P 等于 NP，证明会长什么样？ 卡普的回答很干脆：**它会用到我们现在完全没有的概念。**不管结论是等还是不等，证明都会来自盒子外面。 如果真的证明了 P 不等于 NP，世界的反应会是：对于绝大多数实际出现的组合问题，既然它们是 NP 完全的，就不存在高效算法。但还有一点余地，因为 NP 完全只说明“不能对所有实例都快”，不说明“不能对大多数实例快”。所以注意力会转向启发式和近似算法，带着更多宽容，接受“最优解拿不到，好解也行”。 如果证明了 P 等于 NP，冲击是另一个量级。所有解容易验证的问题，都能在多项式时间内求解。那意味着很多今天靠密码学保护的东西会瞬间失去屏障。 ## 稳定匹配：主动出击的人占便宜 Lex 请卡普挑一个他觉得最美的组合算法。 卡普选的是稳定匹配，也叫稳定婚姻问题。 n 个男孩，n 个女孩。每个男孩对女孩有一个偏好排序，每个女孩对男孩也有一个。一个匹配是“稳定”的，意思是：不存在两对情侣，其中男孩更喜欢第二对的女孩，女孩也更喜欢第一对的男孩，于是这两个人想私奔，把原来的伴侣丢下。 1962 年，大卫·盖尔（David Gale）和劳埃德·沙普利（Lloyd Shapley）证明了两件事：**任何一组偏好下，稳定匹配都存在，而且可以用一个极简的算法算出来。** 算法是这样：每个男孩按自己的偏好列表，依次向女孩求婚。女孩收到求婚先暂时接受，但保留换人的权利。如果后来收到更好的，就把原来的甩掉。男孩被拒之后不回头，继续往下一位求婚。女孩的处境只会越来越好，因为她的对象只会向上替换。男孩的处境只会越来越差，因为他只能往下走。 这个过程一定会结束，结束时所有人都匹配上了，而且没有一对想私奔。 更妙的是：**主动求婚的一方拿到的是他能拿到的最好结果。**在每个男孩所有可能处于的稳定匹配中，这个算法给出的那个，对他而言是最好的。反过来说，女孩拿到的是最差的。 > 这里有个给男孩的教训：你应该主动出击，去求婚。（理查德·卡普） 这套东西在现实里真的用。美国的住院医师匹配系统就是这个思路，医院和医学生各自排偏好，跑一个稳定匹配。只不过现实一加约束就崩：如果一对夫妻想被分到同一个城市，稳定匹配立刻变成 NP 难。 卡普还提了一句让人唏嘘的事。盖尔在诺贝尔奖颁出之前去世了，没能分享这份荣誉。2012 年，沙普利和阿尔文·罗思（Alvin Roth）因为稳定匹配理论与市场设计拿了诺贝尔经济学奖。 ## 加一点随机，笨办法就变聪明 拉宾-卡普算法是卡普最得意的作品之一，因为它展示了随机化的力量。 问题很基础：在一个很长的文本里，找一个很短的词出现在哪。 传统做法是组合式的：逐位比对，用失败函数之类的东西跳过不可能的位置。拉宾-卡普算法走的是完全不同的路。 把每个词看成一个数。字母是数字，字母表的大小是进制。然后随机挑一个大素数，把词对应的数对素数取余，得到一个“指纹”。 接着在长文本上滑动一个长度等于目标词大小的窗口，计算每个窗口内容的指纹。这里有个巧妙的性质：窗口往右滑一格，指纹的更新只需要几次算术运算，不用重算整个窗口。 最后，把每个窗口的指纹和目标词的指纹比对。相同就大概率是真的匹配，因为随机素数保证了碰撞概率很低。万一撞上了，回到原文验证一下就行。 这个算法同时拿到了两个好处：计算量小，因为滑动更新很便宜；错误率低，因为随机选的素数让不同字符串撞指纹的概率极小。代价是概率性的正确性，但这个概率可以被压到任意小。 卡普用几个例子解释随机化为什么这么好用。 第一个是选举。理论上，从全国选民里随机抽几千人，最受欢迎的那个候选人几乎必然就是全国计票的结果。现实里当然不行，因为每个选民都想让自己的票被算进去，而且真正的随机抽样做不到，还可能碰上平票。但把人类社会的这些麻烦去掉，数学上它就是成立的。 第二个是素性测试。费马小定理说，如果 n 是素数，那么对 0 到 n-1 之间任何 a，a 的 n-1 次方模 n 都等于 a。反过来说，如果某个 a 让这个等式不成立，n 就肯定不是素数。随机挑几个 a 试一下，如果全过，n 大概率是素数。实际的 Miller-Rabin 测试要更精细一些，因为存在伪素数，但思路就是这个。 第三个是卡普自己做过的工作：数一个逻辑公式集合有多少个解满足其中至少一个。直接数会重复计数，因为一个解可能同时满足好几个公式。 他的办法是把它看成一个 0/1 矩阵。行是公式，列是解，矩阵里元素为 1 表示这个解满足这个公式。目标是数有多少列至少含一个 1。 做法是按每行 1 的个数来抽样行，1 多的行被抽中的概率大。抽到一行之后，沿着这一行里的某个 1 往上走，只在这个 1 第一次出现的那一行计数。这样每个列只会被算一次。最后得到一个统计上稳健的估计。 这套思路背后有一个更普适的原则：**如果一个现象在大多数情况下都出现，那么随机抽一个样本，大概率能撞上它。** 代数恒等式测试也是这样。两个公式长得完全不一样，你想知道它们是不是同一个东西。随机取一组值代进去，如果结果不一致，分歧就暴露了。因为不相等的点太多，随便挑一个就能撞上。 两个公式不同，那它们在大多数取值点上都会不同。随便挑一个点代进去，就能看到分歧。这条原则能用的地方远比直觉多。 ## 最坏情况分析救不了所有人 上面聊的这些，都属于最坏情况分析：不管输入长什么样，算法都必须在这个步数内完成。 卡普对这个框架的评价很清醒。**最坏情况分析证明一个算法永远好，那很好用。如果它证明一个算法的解不总是好，你就得退一步，换个问题问：多经常能拿到好解？** Lex 接了一句：我们习惯了一旦最坏情况很差，就把这个算法扔进垃圾桶。 卡普说，这很不幸。 他举了 SAT 求解器。可满足性问题是 NP 完全的，理论上不该有高效算法。但现实中，工业级的 SAT 求解器能相当稳定地处理几百万个变量的实例，这些实例来自数字电路设计、程序正确性验证等等。 结果是在那些领域里干活的人，习惯性地把可满足性当成一个简单问题。他们不知道、也不需要知道它在理论上的地位。 > 在那些应用领域，SAT 求解器工作得如此之好，以至于那里的人倾向于认为可满足性是个简单问题。（理查德·卡普） 旅行商问题也一样。这是个 NP 难问题，但用整数规划加上一些数学技巧，人们在平面上分布的城市里，可以求出几万个城市的可证明最优解。规模大一点要跑几个月机器，但一两千个城市的实例，很快就能拿到最优解，而且是最优性的严格证明。 这就出了一个很有意思的缺口：理论上不该存在多项式算法，实践上却跑得飞快。 ## 为什么平均情况分析让人失望 那能不能用平均情况分析，系统性地解释“实践上很好”这件事？ 卡普在这件事上有过亲身经历，而且他坦率地承认了失败。 在他完成 NP 完全性的工作之后，他想给组合算法找一点正面的光。既然最坏情况这么悲观，那就研究平均情况、高概率情况。但立刻冒出一个问题：**概率空间是什么？什么叫典型实例？** 这个问题非常难回答。于是他选了省事的做法：做极其简化的假设。 比如生成一张随机图，做法是每次随机选一条边，一直加到边数够了为止。这套模型在数学界被研究得很透。 在这个模型里，他和别人一起证明了一堆漂亮的结果。比如关于哈密顿回路，一条经过每个顶点恰好一次的环。他们能证明：当边数略微超过 n log n（n 是顶点数）时，这样的环几乎必然存在，而且存在一个高概率找到它的启发式算法。 整个圈子沿着这条线出了很多成果，是个很好玩的游乐场，卡普自己也很享受。 > 但学界对这些结果的态度有点冷淡，因为我们做的假设太简化了。过了一段时间，我得出结论：这对实际应用没什么咬合力。（理查德·卡普） 意思是，玩来玩去还是在玩具问题里打转。 Lex 追问：那能不能找出代表性的、真正有现实意义的实例集，就像机器学习那样？机器学习最好的状态，就是拿一个真实数据集，所有会议都在上面比性能。 卡普说，那边没有对应的东西。高德纳曾经收集过各种来源的图，建了一个“动物园”，可以研究算法在不同类型图上的表现。但问题在于，你怎么定义一类你关心的图？这个定义本身就是个非平凡的步骤。 > 没有什么是可以类比于监督学习里的训练集的。在组合问题这一块，我们真的没有那东西。（理查德·卡普） Lex 又问：现在数据集这么庞大，理论计算机科学会不会长出一个经验性的分支？比如拿 Facebook 的社交网络，分析它的子图，得出的结论既在实践上站得住，又在理论圈里被认可。 卡普说，这个还没实现。有一个叫实验算法学的领域，人们有时拿到一些例子家族，有时干脆随机生成，然后报告性能。但没有任何有说服力的证据表明这些样本代表什么。 ## 小电路的假设，如果成立，整个层级会塌掉 在开放问题里，卡普提到他和理查德·利普顿（Richard Lipton）1979 年的一篇论文。 问题是这样：拿一个 NP 里的问题，比如规模固定为 52 的旅行商问题。能不能造一个针对这个规模量身定制的、规模很小的布尔电路？把图的边作为布尔输入喂进去，输出“是否存在一条长度小于 L 的路径”。 换句话说：这个问题有没有多项式大小的电路？ 已知如果 P 等于 NP，那么这些问题会有小电路。反方向呢？**一个问题可以每个规模都有小电路，但却没有统一的、对所有规模都适用的多项式时间算法吗？** 这里的区别在于“统一”。小电路是一族，每个尺寸一张不同的电路图，彼此之间可能毫无结构关系。多项式时间算法是一段程序，处理所有尺寸。 要理解他们证明的结论，得先理解多项式层级。 层级的第一层是 P。第二层是 NP，也就是“存在一个 X，使得某性质成立”这种形式的命题。比如“存在一种着色，使得图可以用这么多颜色染好”。 再往上，是“对所有 X，存在 Y，使得……”。这是第三层。博弈论里就有这种结构：对先手的所有策略，存在后手的一个策略，使得先手获胜。 再往上，“存在 A，对所有 B，存在 C，使得……”。层数越高，问题越难。 卡普和利普顿证明的是：**如果 NP 有小电路，这个层级会塌缩到第二层。**加三个量词、四个量词、任意多量词，都不会让问题变得更难。 这个结论的用法是反证法。层级没塌，说明 NP 大概没有小电路。但卡普自己也承认，这只能算证据，还算不上证明，而且这个证据的性质有点奇怪：它的逻辑是“因为这件事太荒诞了，所以它不会发生”。 他说了一句挺有意思的话：P 不等于 NP 这个命题本身就够荒诞的，所以不管走哪条路，最后都得跟龙正面对上。 ## 神经网络就是电路，但没人知道它在算什么 Lex 把话题引向机器学习。 卡普认为这两个世界差别很大。深度学习的成果基本是经验性的，跟 SAT 求解器的情况类似：观察到在这些实际出现的输入上效果很好，就这样。 他不否认成功。图像处理、机器人、自然语言处理、游戏博弈，都有巨大突破。副作用是，在机器学习界混出名声之后，想变成百万富翁不难，一堆公司愿意开出天价，因为它们相信只要有 AI，什么问题都能解。 但局限也明显。 第一，卷积神经网络在训练集之外的输入上表现惊人地好，可我们没有任何理论能解释为什么。 第二，训练出来的网络极难理解，几乎榨不出什么洞察。它能在你的训练集上工作，也能分辨一张照片是否来自另一个样本，但我们不知道它到底在看什么。哪些特征在区分照片和物体，很难刻画出来。 Lex 提了一个有意思的类比：你说的“为某个规模定制的小电路”，神经网络不就是小电路吗？ 卡普说，某种意义上是的，但神经网络算不上程序。他随即修正了一下：它当然是一个算法，是一个可计算函数，给它输入就能算出输出。但它没有对输入做算法式操作的那种结构。 > 如果要在图像里识别什么，你不知道图像的哪些特征真正决定了电路在干什么。电路非常精细复杂，你期待的那些简单特征，比如物体的边缘，并没有从电路结构里浮现出来。（理查德·卡普） Lex 反问：人看不清这层，电路自己却清楚。 卡普说，对。就像人类大脑对自己怎么工作也不清楚，但我们能互相解释推理过程，这正是认知科学和心理学存在的理由。 Lex 顺着说，也许“对人类可解释”这件事被高估了。 卡普承认有这个可能，但也补了一句：至少视觉系统、听觉系统，我们确实理解了一些原理。而更深的认知任务，我们确实没有。 ## 基因编辑：把生物系统拉进算法的世界 卡普做过生物信息学的工作。Lex 问他，人类的智能，全部编码在 DNA 里，这件事是否让他惊叹。 卡普说惊叹，更惊叹的是我们开始学会编辑 DNA 了。 > 能取一段序列，在基因组里找到它，然后对它做点什么。这真的把生物系统拉进了算法的世界。（理查德·卡普） 但他马上提到伦理问题。要区分两种情况：编辑一个个体，和编辑生殖细胞。后者意味着所有后代都会受影响。即便是编辑个体，也有大量的傲慢在里面：你假定敲掉某个基因会带来好处，可你不知道副作用是什么。 他说基因编辑在农业和医学上都有巨大潜力，但严重的伦理问题一定会摆到台面上。 算法在这一侧能做的，是分析基因组数据。搞清楚哪些基因在细胞里起作用、在什么条件下起作用，哪些蛋白质影响彼此、哪些有物理相互作用。还能对蛋白质测序并修改它们。 这算不算计算机科学问题？卡普说，这是大数据统计问题，肯定算。生物数据集在膨胀，对祖先的追溯、对疾病倾向的评估、按基因组做个性化治疗，全都在这条线上。 ## 为什么普通人也会被数学吸引 Lex 问了一个传播学的问题。YouTube 上有个频道叫 Numberphile，专门讲数学想法，是最受欢迎的科学频道之一。观众即使听不懂在讲什么，也会被吸引。这种吸引力来自哪里？ 卡普的回答很实在。你能做到一些了不起的事：检验一个大数是不是素数，解一些传教士与野人的小谜题。这是一种成就感，是解谜。 再往上一层，是推理本身的力量。你能以铁一般的方式证明三角形内角和是 180 度。 > 这是对现实世界之混乱的一种逃离。在现实世界里，什么都证明不了。（理查德·卡普） 他还补了一句带点自嘲的话：geek 的另一个特点，是未必具备情绪智力，所以他们能活在抽象世界里，不必去掌握与人打交道的复杂性。 这句话放在整场访谈里回看，其实埋了一根线。他后面讲自己父亲、讲教书、讲学生，讲的都是他后来学会的那部分。 ## Mark IV、Univac，和母亲的建议 回到 1955 年。 Mark IV 占满一整个房间，比他们录访谈的那间办公室大得多。人可以在里面走动，两侧是成排的继电器。机器有时会因为真正的虫子落在开关上而故障。 卡普说他从没用那台机器做过任何实际用途的事。实验室后来弄到了一台早期商用计算机，Univac，2000 个字的存储。 2000 个字。这意味着内存分配是一门艺术。从一个字取数据到另一个字，访问时间取决于字的编号，所以怎么安排存储位置能取数快，需要动脑子。 Lex 问他，是不是被这种“物理地做数学的机器”吸引。 卡普说不是，他感兴趣的是底层的算法。 那当年能想象六十年后全世界有几十亿台计算机吗？ 不能。但实验室里有一种感觉：这是未来的浪潮。他母亲起了作用，她告诉他，数据处理会变得非常重要，他应该进去。 > 我母亲是个聪明的女人。（理查德·卡普） 他说，当时的感觉是这东西会改变世界，但完全没想到个人计算。没想到我们会把计算机装进口袋里到处走。 至于 AI，那时候不在他的雷达上。他读过图灵的论文，就是提出图灵测试的那篇《计算机器与智能》。但他认为图灵测试不够格，因为它太主观，没法用来校准一个算法有多智能。 ## 没有程序能超过六个月大的婴儿 Lex 把话题推到智能本身：能不能造出在推理上和人一样、在我们看来同样智能的算法？ 卡普的回答是：开放问题。但他的倾向很清楚。 他认为已有的成果，绝大多数都运行在一套非常有限的规则里，针对非常精确的单一任务。这跟人脑里发生的事情差别很大。人要在变化的环境中运作，有情绪，有探索环境的身体，有直觉，有欲望。他在当前所谓 AI 的成就里，看不到任何东西接近这种能力。 > 我不认为有任何计算机程序，在世界理解这件事上超过了一个六个月大的婴儿。（理查德·卡普） 那如果坚持一个前提：大脑本质上就是一大堆互相连接的开关。原则上，只要搞清楚连接结构、刻画清楚每个开关，就能在外面造一个仿真。 卡普承认这在原则上是存在的证明。但他说，**那不会是我们最终解决这个问题的方式，这条路走不通。**要去获取那种级别的信息，几乎不可能。 Lex 追问意识。主观体验这件事，我们完全没有头绪。这样一张开关网络，能造出“知道自己”这种东西吗？ 卡普说，如果你想把“知道自己”严格定义出来，会遇到巨大困难。 他知道有很多人相信通用智能可以实现，有些人甚至确信奇点会到来，机器会超越我们，然后不断自我学习，把人类降为劣等物种。 > 我怀疑这永远不会实现。（理查德·卡普） 理由只有一个：语音、机器人、自然语言处理、灵活的计算助手，这些成就没有一个接近那个级别的认知。 Lex 抛出了摩尔定律这个反驳：我们习惯线性思考，想象不出从 Mark I 到 iPhone X 的跨度。会不会指数增长再一次让人大吃一惊？ 卡普的回答是：**任何常数因子的改进都改变不了局面。**按我们现在对认知需要什么的理解，把开关速度提高一千倍、一百万倍，在真正理解那张开关网络背后的组织原理之前，都没有用。 ## 什么是组合算法 Lex 请卡普从最基础讲起。访谈到了这儿，气氛最接近课堂。 组合算法处理的是离散对象的系统。这些对象可以处于不同状态，或者取一组离散值中的某个值，需要被安排或挑选，以最小化某个成本函数，或者证明某种组合构型存在。 图是什么？ 一组点，其中某些点对之间用线连起来，这些线叫边。在不同应用里，它表示离散对象之间的互联关系：数字电路里开关之间的连接，人类社群里的通信模式，公路系统里城市之间的道路。 边可以是有向的，也可以是无向的。通信网络里，无向边表示信息双向流动，有向边表示单向。边上还可以带权，比如公路的距离。 然后是应用的列举，卡普一口气给了一串。 学校排课：顶点是课程，边表示约束，某些课不能同时开，某些老师只在特定时段可用。 分配问题：每个男孩到每个女孩一条带权边，权是成本。 逻辑电路设计：要找一组门电路，互相连接起来实现某个逻辑函数。比如“输入里至少 k 个为 1 时输出是，否则输出否”，需要多少个门才够。 Lex 说他最喜欢网络流，因为太直观了。管道和水，可以映射到通信网络、交通流，视觉上和智力上都吸引人。 卡普解释：边表示通道，上面流着某种商品，可能是天然气、水、信息，也可能是产品从一个工序流到下一个工序。边上有容量，表示流速上限。中心问题是，给定这样一张网络，从源点到汇点的最大流速是多少。 ## 第一批证明最大流属于多项式时间的人 这是卡普和杰克·埃德蒙兹（Jack Edmonds）合作的工作。 > 我想我们是第一批给出形式证明的人：网络最大流问题可以在多项式时间内求解。（理查德·卡普） Lex 说他第一次学到这个结论时非常惊讶。最大流居然有多项式算法，一个漂亮又快的算法。 多项式时间到底是什么意思？ 卡普从输入开始讲。一个问题有一组输入数据，比如一张图，每个顶点、每条边、每条边的容量。算法是一段程序，基本操作是加减乘除、比较大小。 目标是用最少的计算步数得到答案。这里的“一步”就是一次这样的操作。 如果所需步数，作为输入规模（顶点数、边数）的函数，只按某个固定幂次增长，就叫多项式时间。线性算法是步数与规模成正比，平方算法是步数与规模的平方成正比。 **理论家把“高效”定义成这个。**这个定义可以商榷：一个跑到输入规模一万次方的算法，显然谈不上高效。实践里真正有意义的跳跃，往往是从 n² 降到 n log n 或者线性，因为网络规模可以到几百万，任何高于 n log n 的东西都太慢了。 那 NP 是什么？ **NP 是那些可能很难求解，但拿到一个解之后可以在多项式时间内验证的问题类。** 卡普用团问题举例。一张图里有没有大小为 k 的完全子图，其中任意两个顶点都相邻？这个问题很难。但如果有人递给你一组顶点，问这组是不是团，你只需要把组内所有顶点对之间的边都检查一遍，那是多项式时间。 找团很难，验团很容易。这类问题就叫非确定性多项式时间，也就是 NP。 有一个显然的包含关系：**P 里的每个问题也在 NP 里。**能精确求解，当然也能验证解。反过来成不成立，就没人知道了。 排课也是这样。拿到一张排好的课表，你能快速验证它满足所有要求。这不意味着你能快速找到这样一张课表。 直觉上，能验证的类会比能求解的类大得多。这里必须加一句“看起来”，因为没人证明过。 ## 为什么敢赌 P 不等于 NP Lex 让卡普押上全部身家赌一把。 卡普赌 P 不等于 NP。理由很朴素：有些问题已经存在了几个世纪，数学界密集研究了很久，特别是 P 与 NP 提出之后的这五十年，仍然没有找到多项式时间算法。 他举的例子是因数分解，可以追溯到高斯。素数就是不能写成两个大于一的整数乘积的数。91 等于 7 乘 13，这好办。但给你一个 20 位、30 位的数，你大概就束手无策了。反过来，一旦有人把因子给你，你验证乘起来对不对是瞬间的事。 这里有一层现实含义，卡普没有明说但很明显：**今天大量公钥密码系统的安全性，就架在“因数分解没有高效算法”这个信念上。**它算不上定理，只能算信念。 > 如果 P 不等于 NP，我们同时也就知道，几乎所有标准的组合问题都不能在多项式时间内求解。（理查德·卡普） 这就是 1971 年那篇论文的分量。它把成百上千个看起来无关的问题绑成了一束：要么全都能高效求解，要么全都不行。攻破其中一个，整束就全破了。 而这一切的起点，是库克证明的那件事：SAT 和 NP 里的任何问题一样难。 卡普在访谈里对库克的工作给了很高的评价。他说看库克的证明，理解为什么成立并不算太难，但含义令人震惊。**所有解容易验证的问题，全都能重写成同一个问题的形式。** ## 稳定匹配：主动出击的人占便宜 Lex 请卡普挑一个他心目中最美的组合算法。 卡普选的是稳定匹配，也叫稳定婚姻问题。 n 个男孩，n 个女孩。每个男孩对女孩有一个偏好排序，每个女孩对男孩也有一个。一个匹配是“稳定”的，意思是：不存在两对情侣，其中男孩更喜欢第二对的女孩，女孩也更喜欢第一对的男孩，于是这两个人想私奔，把原来的伴侣丢下。 1962 年，大卫·盖尔（David Gale）和劳埃德·沙普利（Lloyd Shapley）证明了两件事：**任何一组偏好下，稳定匹配都存在，而且可以用一个极简的算法算出来。** 算法是这样：每个男孩按自己的偏好列表，依次向女孩求婚。女孩收到求婚先暂时接受，但保留换人的权利。如果后来收到更好的，就把原来的甩掉。男孩被拒之后不回头，继续往下一位求婚。女孩的处境只会越来越好，因为她的对象只会向上替换。男孩的处境只会越来越差，因为他只能往下走。 这个过程一定会结束，结束时所有人都匹配上了，而且没有一对想私奔。 更妙的是：**主动求婚的一方拿到的是他能拿到的最好结果。**在每个男孩所有可能处于的稳定匹配中，这个算法给出的那个，对他而言是最好的。反过来说，女孩拿到的是最差的。 > 这里有个给男孩的教训：你应该主动出击，去求婚。（理查德·卡普） 这套东西在现实里真的用。美国的住院医师匹配系统就是这个思路，医院和医学生各自排偏好，跑一个稳定匹配。现实一加约束就崩：如果一对夫妻想被分到同一个城市，稳定匹配立刻变成 NP 难。 卡普还提了一句让人唏嘘的事。盖尔在诺贝尔奖颁出之前去世了，没能分享这份荣誉。2012 年，沙普利和阿尔文·罗思（Alvin Roth）因为稳定匹配理论与市场设计拿了诺贝尔经济学奖。 ## 加一点随机，笨办法就变聪明 拉宾-卡普算法是卡普最得意的作品之一，因为它展示了随机化的力量。 问题很基础：在一个很长的文本里，找一个很短的词出现在哪。 传统做法是组合式的：逐位比对，用失败函数之类的东西跳过不可能的位置。拉宾-卡普算法走的是完全不同的路。 把每个词看成一个数。字母是数字，字母表的大小是进制。然后随机挑一个大素数，把词对应的数对素数取余，得到一个“指纹”。 接着在长文本上滑动一个长度等于目标词大小的窗口，计算每个窗口内容的指纹。这里有个巧妙的性质：窗口往右滑一格，指纹的更新只需要几次算术运算，不用重算整个窗口。 最后，把每个窗口的指纹和目标词的指纹比对。相同就大概率是真的匹配，因为随机素数保证了碰撞概率很低。万一撞上了，回到原文验证一下就行。 这个算法同时拿到了两个好处：计算量小，因为滑动更新很便宜；错误率低，因为随机选的素数让不同字符串撞指纹的概率极小。代价是概率性的正确性，但这个概率可以被压到任意小。 卡普用几个例子解释随机化为什么这么好用。 第一个是选举。理论上，从全国选民里随机抽几千人，最受欢迎的那个候选人几乎必然就是全国计票的结果。现实里当然不行，因为每个选民都想让自己的票被算进去，而且真正的随机抽样做不到，还可能碰上平票。把人类社会的这些麻烦去掉，数学上它就是成立的。 第二个是素性测试。费马小定理说，如果 n 是素数，那么对 0 到 n-1 之间任何 a，a 的 n-1 次方模 n 都等于 a。反过来说，如果某个 a 让这个等式不成立，n 就肯定不是素数。随机挑几个 a 试一下，如果全过，n 大概率是素数。实际的 Miller-Rabin 测试要更精细一些，因为存在伪素数，但思路就是这个。 第三个是卡普自己做过的工作：数一个逻辑公式集合有多少个解满足其中至少一个。直接数会重复计数，因为一个解可能同时满足好几个公式。 他的办法是把它看成一个 0/1 矩阵。行是公式，列是解，矩阵里元素为 1 表示这个解满足这个公式。目标是数有多少列至少含一个 1。 做法是按每行 1 的个数来抽样行，1 多的行被抽中的概率大。抽到一行之后，沿着这一行里的某个 1 往上走，只在这个 1 第一次出现的那一行计数。这样每个列只会被算一次。最后得到一个统计上稳健的估计。 这套思路背后有一个更普适的原则：**如果一个现象在大多数情况下都出现，那么随机抽一个样本，大概率能撞上它。** 代数恒等式测试也是这样。两个公式长得完全不一样，你想知道它们是不是同一个东西。随机取一组值代进去，如果结果不一致，分歧就暴露了。因为不相等的点太多，随便挑一个就能撞上。 两个公式不同，那它们在大多数取值点上都会不同。随便挑一个点代进去，就能看到分歧。这条原则能用的地方远比直觉多。 ## 最坏情况分析救不了所有人 上面聊的这些，都属于最坏情况分析：不管输入长什么样，算法都必须在这个步数内完成。 卡普对这个框架的评价很清醒。**最坏情况分析证明一个算法永远好，那很好用。如果它证明一个算法的解不总是好，你就得退一步，换个问题问：多经常能拿到好解？** Lex 接了一句：我们习惯了一旦最坏情况很差，就把这个算法扔进垃圾桶。 卡普说，这很不幸。 他举了 SAT 求解器。可满足性问题是 NP 完全的，理论上不该有高效算法。但现实中，工业级的 SAT 求解器能相当稳定地处理几百万个变量的实例，这些实例来自数字电路设计、程序正确性验证等等。 结果是在那些领域里干活的人，习惯性地把可满足性当成一个简单问题。他们不知道、也不需要知道它在理论上的地位。 > 在那些应用领域，SAT 求解器工作得如此之好，以至于那里的人倾向于认为可满足性是个简单问题。（理查德·卡普） 旅行商问题也一样。这是个 NP 难问题，但用整数规划加上一些数学技巧，人们在平面上分布的城市里，可以求出几万个城市的可证明最优解。规模大一点要跑几个月机器，但一两千个城市的实例，很快就能拿到最优解，而且是最优性的严格证明。 这里就出了一个很有意思的缺口：理论上不该存在多项式算法，实践上却跑得飞快。 ## 为什么平均情况分析让人失望 那能不能用平均情况分析，系统性地解释“实践上很好”这件事？ 卡普在这件事上有过亲身经历，而且他坦率地承认了失败。 在他完成 NP 完全性的工作之后，他想给组合算法找一点正面的光。既然最坏情况这么悲观，那就研究平均情况、高概率情况。立刻冒出一个问题：**概率空间是什么？什么叫典型实例？** 这个问题非常难回答。于是他选了省事的做法：做极其简化的假设。 比如生成一张随机图，做法是每次随机选一条边，一直加到边数够了为止。这套模型在数学界被研究得很透。 在这个模型里，他和别人一起证明了一堆漂亮的结果。比如关于哈密顿回路，一条经过每个顶点恰好一次的环。他们能证明：当边数略微超过 n log n（n 是顶点数）时，这样的环几乎必然存在，而且存在一个高概率找到它的启发式算法。 整个圈子沿着这条线出了很多成果，是个很好玩的游乐场，卡普自己也很享受。 > 但学界对这些结果的态度有点冷淡，因为我们做的假设太简化了。过了一段时间，我得出结论：这对实际应用没什么咬合力。（理查德·卡普） 意思是，玩来玩去还是在玩具问题里打转。 Lex 追问：那能不能找出代表性的、真正有现实意义的实例集，就像机器学习那样？机器学习最好的状态，就是拿一个真实数据集，所有会议都在上面比性能。 卡普说，那边没有对应的东西。高德纳曾经收集过各种来源的图，建了一个“动物园”，可以研究算法在不同类型图上的表现。问题在于，你怎么定义一类你关心的图？这个定义本身就是个非平凡的步骤。 > 没有什么是可以类比于监督学习里的训练集的。在组合问题这一块，我们真的没有那东西。（理查德·卡普） Lex 又问：现在数据集这么庞大，理论计算机科学会不会长出一个经验性的分支？比如拿 Facebook 的社交网络，分析它的子图，得出的结论既在实践上站得住，又在理论圈里被认可。 卡普说，这个还没实现。有一个叫实验算法学的领域，人们有时拿到一些例子家族，有时干脆随机生成，然后报告性能。但没有任何有说服力的证据表明这些样本代表什么。 ## 小电路的假设一旦成立，层级会整个塌掉 在开放问题里，卡普提到他和理查德·利普顿（Richard Lipton）1979 年的一篇论文。 问题是这样：拿一个 NP 里的问题，比如规模固定为 52 的旅行商问题。能不能造一个针对这个规模量身定制的、规模很小的布尔电路？把图的边作为布尔输入喂进去，输出“是否存在一条长度小于 L 的路径”。 换句话说：这个问题有没有多项式大小的电路？ 已知如果 P 等于 NP，那么这些问题会有小电路。反方向呢？**一个问题可以每个规模都有小电路，但却没有统一的、对所有规模都适用的多项式时间算法吗？** 区别在于“统一”。小电路是一族，每个尺寸一张不同的电路图，彼此之间可能毫无结构关系。多项式时间算法是一段程序，处理所有尺寸。 要理解他们证明的结论，得先理解多项式层级。 层级的第一层是 P。第二层是 NP，也就是“存在一个 X，使得某性质成立”这种形式的命题。比如“存在一种着色，使得图可以用这么多颜色染好”。 再往上，是“对所有 X，存在 Y，使得……”。这是第三层。博弈论里就有这种结构：对先手的所有策略，存在后手的一个策略，使得先手获胜。 再往上，“存在 A，对所有 B，存在 C，使得……”。层数越高，问题越难。 卡普和利普顿证明的是：**如果 NP 有小电路，这个层级会塌缩到第二层。**加三个量词、四个量词、任意多量词，都不会让问题变得更难。 这个结论的用法是反证法。层级没塌，说明 NP 大概没有小电路。卡普自己也承认，这只能算证据，还算不上证明，而且这个证据的性质有点奇怪：它的逻辑是“因为这件事太荒诞了，所以它不会发生”。 他说了一句挺有意思的话：P 不等于 NP 这个命题本身就够荒诞的，所以不管走哪条路，最后都得跟龙正面对上。 ## 神经网络就是电路，但没人知道它在算什么 Lex 把话题引向机器学习。 卡普认为这两个世界差别很大。深度学习的成果基本是经验性的，跟 SAT 求解器的情况类似：观察到在这些实际出现的输入上效果很好，就这样。 他不否认成功。图像处理、机器人、自然语言处理、游戏博弈，都有巨大突破。副作用是，在机器学习界混出名声之后，想变成百万富翁不难，一堆公司愿意开出天价，因为它们相信只要有 AI，什么问题都能解。 局限也明显。 第一，卷积神经网络在训练集之外的输入上表现惊人地好，可我们没有任何理论能解释为什么。 第二，训练出来的网络极难理解，几乎榨不出什么洞察。它能在你的训练集上工作，也能分辨一张照片是否来自另一个样本，但我们不知道它到底在看什么。哪些特征在区分照片和物体，很难刻画出来。 Lex 提了一个有意思的类比：你说的“为某个规模定制的小电路”，神经网络不就是小电路吗？ 卡普说，某种意义上是的，但神经网络算不上程序。他随即修正了一下：它当然是一个算法，是一个可计算函数，给它输入就能算出输出。但它没有对输入做算法式操作的那种结构。 > 如果要在图像里识别什么，你不知道图像的哪些特征真正决定了电路在干什么。电路非常精细复杂，你期待的那些简单特征，比如物体的边缘，并没有从电路结构里浮现出来。（理查德·卡普） Lex 反问：人看不清这层，电路自己却清楚。 卡普说，对。就像人类大脑对自己怎么工作也不清楚，但我们能互相解释推理过程，这正是认知科学和心理学存在的理由。 Lex 顺着说，也许“对人类可解释”这件事被高估了。 卡普承认有这个可能，但也补了一句：至少视觉系统、听觉系统，我们确实理解了一些原理。更深的认知任务，我们确实没有。 ## 基因编辑：把生物系统拉进算法的世界 卡普做过生物信息学的工作。Lex 问他，人类的智能全部编码在 DNA 里，这件事是否让他惊叹。 卡普说惊叹，更惊叹的是我们开始学会编辑 DNA 了。 > 能取一段序列，在基因组里找到它，然后对它做点什么。这真的把生物系统拉进了算法的世界。（理查德·卡普） 但他马上提到伦理问题。要区分两种情况：编辑一个个体，和编辑生殖细胞。后者意味着所有后代都会受影响。即便是编辑个体，也有大量的傲慢在里面：你假定敲掉某个基因会带来好处，可你不知道副作用是什么。 他说基因编辑在农业和医学上都有巨大潜力，但严重的伦理问题一定会摆到台面上。 算法在这一侧能做的，是分析基因组数据。搞清楚哪些基因在细胞里起作用、在什么条件下起作用，哪些蛋白质影响彼此、哪些有物理相互作用。还能对蛋白质测序并修改它们。 这算不算计算机科学问题？卡普说，这是大数据统计问题，肯定算。生物数据集在膨胀，对祖先的追溯、对疾病倾向的评估、按基因组做个性化治疗，全都在这条线上。 ## 为什么普通人也会被数学吸引 Lex 问了一个传播学的问题。YouTube 上有个频道叫 Numberphile，专门讲数学想法，是最受欢迎的科学频道之一。观众即使听不懂在讲什么，也会被吸引。这种吸引力来自哪里？ 卡普的回答很实在。你能做到一些了不起的事：检验一个大数是不是素数，解一些传教士与野人的小谜题。这是成就感，是解谜。 再往上一层，是推理本身的力量。你能以铁一般的方式证明三角形内角和是 180 度。 > 这是对现实世界之混乱的一种逃离。在现实世界里，什么都证明不了。（理查德·卡普） 他还补了一句带点自嘲的话：geek 的另一个特点，是未必具备情绪智力，所以他们能活在抽象世界里，不必去掌握与人打交道的复杂性。 这句话放在整场访谈里回看，其实埋了一根线。他后面讲自己父亲、讲教书、讲学生，讲的都是他后来学会的那部分。 ## Mark IV、Univac，和母亲的建议 回到 1955 年。 Mark IV 占满一整个房间，比他们录访谈的那间办公室大得多。人可以在里面走动，两侧是成排的继电器。机器有时会因为真正的虫子落在开关上而故障。 卡普说他从没用那台机器做过任何实际用途的事。实验室后来弄到了一台早期商用计算机，Univac，2000 个字的存储。 2000 个字。这意味着内存分配是一门艺术。从一个字取数据到另一个字，访问时间取决于字的编号，所以怎么安排存储位置能取数快，需要动脑子。 Lex 问他，是不是被这种“物理地做数学的机器”吸引。 卡普说不是，他感兴趣的是底层的算法。 那当年能想象六十年后全世界有几十亿台计算机吗？ 不能。但实验室里有一种感觉：这是未来的浪潮。他母亲起了作用，她告诉他，数据处理会变得非常重要，他应该进去。 > 我母亲是个聪明的女人。（理查德·卡普） 他说，当时的感觉是这东西会改变世界，但完全没想到个人计算。没想到我们会把计算机装进口袋里到处走。 至于 AI，那时候不在他的雷达上。他读过图灵的论文，就是提出图灵测试的那篇《计算机器与智能》。他认为图灵测试不够格，因为它太主观，没法用来校准一个算法有多智能。 ## 没有程序能超过六个月大的婴儿 Lex 把话题推到智能本身：能不能造出在推理上和人一样、在我们看来同样智能的算法？ 卡普的回答是：开放问题。他的倾向很清楚。 已有的成果，绝大多数都运行在一套非常有限的规则里，针对非常精确的单一任务。这跟人脑里发生的事情差别很大。人要在变化的环境中运作，有情绪，有探索环境的身体，有直觉，有欲望。他在当前所谓 AI 的成就里，看不到任何东西接近这种能力。 > 我不认为有任何计算机程序，在世界理解这件事上超过了一个六个月大的婴儿。（理查德·卡普） 那如果坚持一个前提：大脑本质上就是一大堆互相连接的开关。原则上，只要搞清楚连接结构、刻画清楚每个开关，就能在外面造一个仿真。 卡普承认这在原则上是存在的证明。但他说，**那不会是我们最终解决这个问题的方式，这条路走不通。**要去获取那种级别的信息，几乎不可能。 Lex 追问意识。主观体验这件事，我们完全没有头绪。这样一张开关网络，能造出“知道自己”这种东西吗？ 卡普说，如果你想把“知道自己”严格定义出来，会遇到巨大困难。 他知道有很多人相信通用智能可以实现，有些人甚至确信奇点会到来，机器会超越我们，然后不断自我学习，把人类降为劣等物种。 > 我怀疑这永远不会实现。（理查德·卡普） 理由只有一个：语音、机器人、自然语言处理、灵活的计算助手，这些成就没有一个接近那个级别的认知。 Lex 抛出了摩尔定律这个反驳：我们习惯线性思考，想象不出从 Mark I 到 iPhone X 的跨度。会不会指数增长再一次让人大吃一惊？ 卡普的回答是：**任何常数因子的改进都改变不了局面。**按我们现在对认知需要什么的理解，把开关速度提高一千倍、一百万倍，在真正理解那张开关网络背后的组织原理之前，都没有用。 ## 两次“原来我行了”的时刻 访谈快结束时，Lex 问：如果能重历人生中某个时刻，抛开家庭不谈，只挑那个让你真正快乐、或者深刻改变了你方向的瞬间，会选哪个？ 卡普说自己本科时是个懒学生，研究生第一年也是。 转折点是他开始做研究的时候。他有过几个暑期工作，在其中能够做出贡献，有了自己的想法。然后是一门关于数学方法和运筹学的课，他把材料整个吞了下去，考分比班上第二名高了 20 分，引起了教师的注意。 > 那让我意识到，我是有一些能力的，我正在往某个方向走。（理查德·卡普） 另一段回忆关于他父亲。 他把 1985 年的图灵奖演讲献给了父亲的记忆。最深的印象是看父亲站在黑板前，徒手画出完美的圆，以及他吸引住那一群参差不齐的八年级学生的能力。 卡普说，他偶尔能溜进父亲的教室旁观。他觉得父亲在讲台上状态最好，整个人活了起来，不只教书，还跟学生闲聊，跟他们打成一片。 他从那里继承来的，是强烈的教书愿望。 他最近退休，很多以前的学生来了。有的跟他做过研究，有的读过他的论文，有的上过他的课。他们谈论他的时候，不谈 1979 年的论文或者 1992 年的论文，谈的是从他的课堂里带走了什么。**不是细节，是方法，是教书的姿态。** 他说自己至少在做教员的早年，备课是模范级别的，每次进教室都准备到牙齿。而充分准备带来的好处，恰恰是能随时偏离教案。 Lex 问给年轻老师的建议。 卡普说，前三名是：准备、准备、准备。 > 准备给你一种从容，能应对课堂上出现的任何情况。如果你发现一种讲法学生没听懂，你可以换一种。如果学生提问，你接得住。（理查德·卡普） 准备到位之后，你能跳舞。能换个说法，能换个角度。 还有一件事：读人。看学生的眼神，从他们的提问里判断他们卡在哪里、接住了什么。 Lex 问，有没有哪些计算机科学的思想，是学生一听就眼睛亮、从此爱上这个领域的？ 卡普说，因人而异。有人几乎不需要推动，自己在跑，只需要偶尔有个人听他说。有人需要推一把。有人需要被说服去跟别人合作，而不是单干。每个人都有自己的起伏，你得把每个学生当人对待，把他最好的一面带出来。 人类很复杂。他说这句话的时候，语气很平。 ## 卡普这条线索里，最该带走的东西 整场对话里，卡普反复在两个位置上停下来。一个是“我能证明它”，另一个是“它在我这儿跑得很好”。 他一生的工作基本都在这两个位置之间搭桥。1971 年那篇论文是把桥搭向悲观的一侧：二十一个问题被证明同样难，谁也别指望侥幸。而拉宾-卡普算法、SAT 求解器的现实表现、旅行商问题的万级城市最优解，是把桥搭向乐观的一侧：理论上不该快的东西，在具体输入上就是快。 这两侧并不矛盾，它们描述的是不同的空间。最坏情况分析划出的是所有输入构成的全集，实际应用落在的是全集里一小块结构良好的区域。卡普承认后者很难刻画，甚至公开说自己在这条路上试过、效果不彰。这种承认本身，比任何结论都值得记住。 他对 AI 的判断也遵循同一个逻辑。他不说深度学习没用，他说我们没有理论解释它为什么有用，也拿不到洞察。这两句话可以同时成立，而且同时成立才是准确的描述。 ## 如果这些内容让你想动手，可以这么做 - 找一本《算法导论》或者 Kleinberg-Tardos，把最大流和稳定匹配这两章读透。卡普在访谈里反复回到这两个算法，理由在于它们展示了结构之美与可证明性能同时成立，实用性反而是次要的。 - 拿一个手上真实的调度、匹配、分配问题，先别急着求最优解。用稳定匹配或者匈牙利算法的思路跑一遍，看看能得到什么。很多现实问题的“足够好”解，代价比追求最优低一个数量级。 - 如果你的系统里有 NP 难问题，去用现成的 SAT 求解器或整数规划求解器试一遍，别因为它理论上难就直接放弃。数字电路设计和旅行商问题的实例都说明，实际出现的输入往往比最坏情况友好得多。 - 想感受随机化的威力，自己实现一遍拉宾-卡普字符串匹配，然后在同一份文本上跟 KMP 比一次。读数不重要，重要的是理解随机指纹为什么能让一个看起来笨的办法跑得又快又稳。 - 写代码做性能判断时，把最坏情况和典型情况当成两个独立问题来问。算法最坏情况差，不代表它在你手上的数据上差。反过来，它在你的数据上跑得好，也不代表它在所有数据上都靠得住。 - 如果你在教课或者带人，把卡普那句话抄下来：准备、准备、准备。准备的目的在换取偏离教案的自由，照本宣科只是它的副产品。 - 找一份讲 1971 年那篇《组合问题之间的可归约性》的讲义读一遍，不必啃原文。搞清楚那 21 个问题怎么互相归约，你对“归约”这个词会有完全不同的体感。 访谈最后，Lex 念了阿西莫夫的一句话作为收尾。 > 我不害怕计算机。我害怕的是没有计算机。（艾萨克·阿西莫夫） 卡普在整场对话里表达的态度，比这句话更沉一点。他不怕计算机，也不认为计算机会在可见的未来超越人。他更在意另一件事：我们以为自己理解了，其实只是观察到了效果好。 这两种担心，一种指向未来，一种指向现在。后一种更值得花时间。