Richard Karp：这些问题要么都容易，要么都不容易

Lex Fridman 开场引用了 Karp 自己写下的一句话：他 13 岁第一次接触平面几何，就被形式证明的力量与优雅深深震撼。Karp 接着讲了一个他从 Michael Rabin 那里听来的故事：Rabin 小时候因为表现不好被赶出教室，在走廊里闲逛，遇到两个年纪较大的学生正被一道题难住。这道题是：两个互不重叠的圆之间，最短距离是多少？

Rabin 的答案是：取两圆圆心的连线，两圆之间的那一段就是最短的。任何别的连接两圆的线段，若在两端各延长一个半径，就会变成连接两个圆心的三段折线，而三段折线不可能比直线更短。Karp 和 Rabin 都觉得这很优雅：纯粹的推理就能确立一个毫无争议的几何事实。三角形内角和为 180 度，也带来同样的乐趣：过一个顶点作对边的平行线，内错角就能给出一个半平面。Karp 说，让人惊讶的是这个证明如此简单，同时又如此令人信服。

几何中的图形部分仍然很重要，尽管他的三维空间想象力很差。他很难想象曲面和超平面，后来做线性规划和整数规划时，需要他想象多面体上的最高点，这一点就成了问题。图形能带来动力，真正的工具是代数。他说，欧几里得几何本身并没有特别塑造他之后的组合研究，留下来的是一种习惯：被一个干净利落的论证拦住脚步。

被问到设计算法时脑子里想的是什么，Karp 的回答几乎像机械运转一样直接。算法通常就是一个内层循环的反复执行。他会想象与目标解的距离不断缩小，直到恰好命中。每一步都必须更接近一点，而且需要确定它一定会收敛。谈到旅行商问题时，他喜欢看某个函数被逐步最小化，一步步逼近最优值，他觉得这很迷人。Fridman 把这件事分成两部分：一是对解长什么样的直觉，二是在给定复杂度下证明它会收敛的那套繁琐证明。Karp 认为奥妙在于前一种观察：差距单调地缩小，各项指标不断改善，最后就碰到了最优值。

Don Knuth 曾描述过一类人：他们从审视计算过程的结构中获得很大的审美乐趣，并把这类人称为 geek。Karp 记得自己意识到自己也是这种人的那一刻：有人向他演示用于分配问题的匈牙利算法。设有 n 个男孩和 n 个女孩，以及一张配对成本矩阵，目标是找到总成本最低的一一配对，禁止的配对可以视为无穷大。关键的观察只有一句话：从任一行或任一列减去同一个常数，最优的排列不会改变，因为每个完整配对的总和都会减少同样的数，比较结果因此不受影响。

算法从一个非负矩阵出发，不断从行或列中减去常数，并保证不出现负数，直到出现一组全是零、彼此不冲突的完整排列。这组排列就是成本最低的。实际上，若只做减法，就把步骤简化过头了：要对一些行和列做减法，同时对另一些行和列加上同一个数，这样原有的零保持为零，而总成本仍然下降。要处理哪些行和列，是靠矩阵上的一种最短路径搜索找出来的。多项式时间，而且井井有条。Karp 说，如果他有动手能力，大概会喜欢木工，把一块料雕琢成漂亮的器物。迭代算法的系统性也给他同样的快乐。他小时候常在脑子里做四位数的乘法取乐，还会从 1 开始一直翻倍，直到记不住为止，以此哄自己入睡。他在波士顿郊外一个 skee-ball 游戏摊做暑期工，负责吆喝招揽顾客，喊的是“快来，大家快来，五分钱就能玩”。这让他和一些对学术毫无兴趣的同事站在了一起，而他的心算让这些同事印象深刻。

Fridman 提到，Numberphile 是网上观看量最高的科学频道之一，即使观众跟不上细节，也愿意一直看下去。Karp 的解释很实际：你可以检验一个大数是不是素数，也可以解开传教士与食人族的小谜题。这些都是一种成就，是解谜的乐趣。再往上一层，你还能以无可辩驳的方式证明三角形内角和为 180 度。这是一种逃离现实世界纷乱的办法，因为现实世界里几乎没有什么东西能被证明。他补充说，geek 的另一个特点是，他们不一定具备很高的情绪智力，所以能生活在抽象之中，而不必去掌握与人打交道的复杂之处。

1955 年，Karp 以哈佛博士生的身份加入了 Howard Aiken 主持的计算实验室，那里有 Mark I 和 Mark IV。Mark IV 占据的房间，比他们现在所在的办公室大得多。人可以走进机器内部，从成排的继电器旁边走过。机器有时会因为故障停摆，而故障真的是飞虫造成的，它们落在了触点上。他从未用那台机器做过任何实际运算。后来实验室又购入了一台 UNIVAC，存储容量为 2000 个字。内存分配是一门技艺：从一个字到另一个字的存取时间，取决于字的编号，所以要精心安排存储，才能让取数更快。

Fridman 问，他是不是被那种具体化了的数学吸引。完全不是，他着迷的是背后的算法。Fridman 又问，六十年后，他能想象会有数十亿台计算机吗？他想象不到，不过实验室里的人都觉得这是大势所趋。他母亲告诉他，数据处理将会非常重要，他应该往这个方向发展。“她是个聪明的女人。”他说。他认为这会改变世界，却没有预料到个人电脑，更想象不到人们会把计算机装在口袋里四处走。AI 当时不在他的视线之内，不过他确实读过 Turing 的《计算机器与智能》。他不认为图灵测试（Turing test）是个好测试：它太主观了，也不是衡量一个算法有多聪明的恰当方式。

Karp 说，更深的问题在于，人类水平的智能究竟能否实现。现在被称为 AI 的东西，大多是在有限的规则之内，针对一个精确的任务运行。人类则处于不断变化的环境中，有情绪，有会四处探索的身体，有直觉，也有欲望。他认为当前的任何成果都没有接近这一点。他认为，没有任何计算机程序能在理解世界方面超过一个六个月大的婴儿。被问到图灵机（Turing machine）原则上能否与人类相当时，他持怀疑态度。支持的理由来自大脑本身：如果接受它是一个由海量相互连接的开关构成的系统，那么原则上就可以刻画每一个开关、描绘出它们的线路，再把它模拟出来。这也许可以算作一个存在性证明，但他认为这并不是解决问题的可行办法，因为获取那么多信息几乎是不可能的。

意识，也就是主观体验、知道自己是谁，是我们完全摸不着头脑的谜。如果想严格地定义“知道自己”，会遇到很多麻烦。他身边有人相信通用智能迟早能够实现；也有人确信奇点将会到来，机器会更多地了解自己，而人类将沦为低等的物种。对此他也持怀疑态度。语音、机器人、自然语言以及灵活的计算机助手等方面的研究，离那种认知水平都还很远。Fridman 提到摩尔定律：人们习惯线性地思考，所以没能预料到从 Mark I 到 iPhone 的飞跃。Karp 认为，任何常数因子层面的改进都改变不了这一点。把开关速度提高一千倍或一百万倍，在我们理解网络背后的组织原理之前，也没有用处。

Karp 说，组合算法处理的是离散的对象：它们处于某些状态，或从一个离散集合中取值，需要加以排列或选择，以使成本最小，或者证明某种构型存在。图是最基本的例子：一组点，由边把其中某些点两两相连。在实际应用中，这些边代表的是互连关系，例如电路中的开关、社区中的通信、城市之间的道路。边可以有方向，也可以没有方向，可以带权，也可以不带权。排课问题把课程放在顶点上，把约束放在边上。分配问题可以看作一张带成本的完全二分图。逻辑设计问的是：要让电路在至少 k 个输入为 1 时输出为真，最少需要多少个门。

Fridman 最喜欢的是网络流：管道、水、交通、通信、供应链，都可以归入其中。边是有容量限制的通道，流动的东西可以是燃气、清水、信息，也可以是在各道工序之间传递的产品。核心问题是：从源点到汇点，最多能以多快的速度输送。Karp 认为，他和 Jack Edmonds 是最早给出形式化证明、说明最大流问题可以在多项式时间内求解的人。Fridman 回忆说，即使在读研究生时，他就对最大流居然有这样漂亮而快速的算法感到惊讶。以两人命名的 Edmonds–Karp 算法，就出自这项工作。在讨论运行时间之前，Karp 想先把多项式时间到底指什么说清楚。

输入是一批数据，例如顶点、边和容量；程序则由加、减、乘、除和比较构成，每一次这样的基本运算算作一步。若算法的步数随输入规模增长，而且增长速度只是某个固定的次幂（线性、平方等等），这个算法就是多项式时间的。理论界把这作为“高效”的定义，Karp 承认这个定义是可以争论的。一个复杂度为 n 的一万次方的算法，按通常的意义来说并不高效。在实践中，真正关键的往往是从 n 的平方降到 n log n 或线性，因为网络可能有数百万个元素，超过 n log n 的做法已经太慢了。在最坏情况下能这样求解的问题类，就是 P。最坏情况几乎就是整个理论的基础：一个算法在大多数输入上很快，却在某一个输入上灾难性地慢，它的复杂度依然很糟。他特别指出这一点，因为实践中一些最有用的算法，在最坏情况下的表现恰恰很差。

NP 指的是这样一类问题：解可能很难找，但给出一个候选解，就可以在多项式时间内检验它对不对。团（clique）问题就是例子：找出一个大小为 k 的完全子图很难；可如果有人给出一组顶点，你只需逐对检查它们之间是否有边，这一过程是多项式时间的。找解很难，验证却容易。P 中的每个问题也属于 NP：能解出来，就能验证。反过来是否成立，正是理论计算机科学的核心问题。排课问题让这种差距显得直观：拿到一张课表，你可以很快检查它是否满足各项约束，但这并不代表你能很快排出一张来。验证看起来比求解容易得多，因此 NP 看起来比 P 大得多。Karp 一再强调“看起来”这个词，因为我们其实并不知道。

如果 Fridman 要他把身家都押上，Karp 会押 P 不等于 NP。理由很直接：这些容易检验的问题中，有些已经存在了几个世纪，数学界对它们做过大量研究；而在提出 P 对 NP 问题之后的五十年里，研究更加深入，却始终没有找到多项式算法。因数分解可以一直追溯到 Gauss。91 是 7 乘以 13。二三十位的数就让人无从下手。可一旦有人把因子告诉你，把它们乘回去就是瞬间的事。如果 P 等于 NP，那么每个解都能被快速检验的问题，实际上都能在多项式时间内求解。他其实并不相信这一点。沿着 Stephen Cook 的思路，他在证明 NP 中大量问题彼此等价方面起了关键作用：要么它们全都属于 P，要么全都不属于。如果 P 不等于 NP，那么几乎所有标准的组合问题都无法在多项式时间内求解。

Cook 1971 年的结果是第一个、也是最重要的一步：命题逻辑的可满足性问题，与 NP 中任何问题一样难。这里的公式由“与”“或”“非”连接取真或取假的变量构成，问题是：是否存在某种取值，能让整个公式为真。Karp 举的四子句例子是：（A 或 B）、（A 或非 B）、（非 A 或 B）、（非 A 或非 B），它没有任何能让它成立的取值。Cook 证明了，NP 中的每个问题都可以重新表述为 SAT 的一个实例。工具是图灵机：一条纸带、一个读写头，以及一张有限的指令表，指令形式是“如果在某个状态下读到某个符号，就写下什么、移动、改变状态”。真实计算机上的任何算法，都可以转写成在这台机器上运行的程序。任何非确定性多项式时间算法，都是一串这样的移动，而这串移动可以写成一个逻辑公式。

Karp 说，看 Cook 的证明时，弄清它为什么成立并不算太难，但它得出的结论令人吃惊。所有解很容易检验的问题，都可以改写成 SAT。于是 P 对 NP 的问题，就变成了 SAT 是否存在多项式时间算法的问题。Karp 是在 1971 年的一次会议上看到这篇论文的。他意识到，SAT 是一个通用的组合问题。以往的经验让他觉得，许多其他问题似乎也具有同样的通用结构，于是他开始尝试从 SAT 出发做归约。整数规划是他最早想到的例子之一：它仍然是线性不等式，只是变量必须是整数，实际上是 0 或 1，这让问题难了很多。把 SAT 改写成这种形式并不困难：每个变量对应一个取值为 0 或 1 的变量，每个子句对应一个不等式。

团问题，或它的近亲独立集问题，能很好地说明这种翻译具体怎么做。先把 SAT 公式写成若干子句的合取，每个子句则是若干文字的析取。要让整个公式成立，就要从每个子句里挑出一个取真的文字，同时不能既挑某个变量、又挑它的否定。接着，以这些文字的出现位置作为顶点建图。若两个顶点在同一子句里（每个子句只挑一个），或者分别代表同一变量的原值与否定（同一变量不可能既为真又为假），就在它们之间加一条边。这样一来，一个大小与子句数相同的独立集，正对应一组能让公式成立的赋值。Fridman 仍然很难相信，图和逻辑公式竟然能这样相互对应。Karp 多少也有同感。两者能表达的范围完全一样，任何一方都能译成另一方的语言。但能表达的范围相同，不代表计算难度也相同：转换过程也可能让规模迅速膨胀。能确定的只有一点：这些问题要么全部有多项式时间的算法，要么全部没有。

1971 年的那篇论文挑出了 21 个基本问题，涉及打包、覆盖、匹配等，它们都属于 NP，并且证明 SAT 可以改写为其中任何一个。这等于是在提出挑战：同类问题很可能还有更多。Karp 说，NP 完全与 NP 难之间只是一层技术上的区别。判定型问题只回答有没有，比如：是否存在大小为 15 的团？优化型问题则给出一个具体的数，比如：最大的团有多大？NP 中最难的判定型问题是 NP 完全的，对应的优化问题则是 NP 难的，两者的等价关系链条是一样的。如果有人证明了 P 等于 NP，或者证明它不等于 NP，那样的证明会是什么样子？它会用到我们现在还没有的概念。若证明 P 不等于 NP，那么绝大多数组合问题，由于是 NP 完全的，就不会对所有实例都有高效算法。不过仍然有一点希望：不属于 P 只是说明它不能对所有实例都高效求解。人们的注意力会转向启发式算法和近似算法，也会更容易接受它们。若 P 等于 NP，影响就要大得多：所有容易检验的问题，都会变得容易求解。

被问到他见过的最美的组合算法是什么，Karp 选择了稳定匹配（stable matching），也叫稳定婚姻问题。设想要为 n 个男孩和 n 个女孩配对。每个男孩都为女孩排出偏好次序，每个女孩也为男孩排出偏好次序。如果一种一一配对中，不存在这样两对：其中一个男孩更喜欢另一对里的女孩，而那个女孩也更喜欢他，即没有哪两个人想要私奔、撇下各自的伴侣，那么这种配对就是稳定的。医学住院医生分配到医院，也是类似的思路，只是形式不完全相同。无论偏好怎样排列，稳定匹配总是存在的，而且可以用一个简单的算法求出。这个算法由 David Gale 和 Lloyd Shapley 提出，并非 Karp 的工作。

每个男孩都按自己的名单依次求婚。女孩会暂时接受，如果有更好的求婚者出现，她可以放弃原先的人选。男孩从不回头：被拒绝之后，就不会再去试那个女孩。女孩手里的人选只会越来越好；男孩则只会沿着自己的名单往下走。过程结束时，每个人都有了配偶，也没有一对想要私奔。谁得到的好处最多？是求婚的一方：每个男孩至少能得到他在任何其他稳定匹配中所能得到的结果。Karp 说，这对男孩们是一个教训：要主动出击。如果再加一条现实的限制，比如一对夫妻都想去同一座城市，问题就会变成 NP 难的。Gale 在能够分享诺贝尔奖之前就去世了。之后，Shapley 因从这一匹配问题衍生出的思想，与另一位学者共同获得了一项经济学奖。

在自己的算法中，Karp 最喜欢的是 Rabin–Karp 字符串匹配算法，因为它清楚地展示了随机化（randomization）的威力。这个问题很古老：一个很长的字符串中是否含有某个给定的短词？经典方法是组合式的，逐个比较字符，并借助失败函数跳过不可能匹配的位置。Rabin–Karp 则另辟蹊径：把字母当作数字，把字母表的大小当作进制，于是每个单词都变成了一个数。在一个范围内随机选取一个素数，对这个数取余，得到的就是一种指纹，类似哈希。让一个与模式等长的窗口在文本上滑动，窗口每右移一位，只需几次算术运算就能更新指纹，无需重新扫描。然后比较指纹：若相同，很可能就是真正的出现，因为随机选取的素数使碰撞的概率很低；一旦遇到碰撞，再回到原文核对。这样一来，更新的代价很低，出错的概率又很小，而且出错之后可以事后核对。

随机化算法说到底，就是能够抽取一个随机数、为对象分配一个随机数，或者从某个集合中抽样的能力。原则上，一场总统选举可以由随机抽取的几千名选民来决定；样本中最受欢迎的候选人，很可能就是全国的胜者。现实中做不到：每个人都希望自己的选票被计入，无法做到纯粹的抽样，还会出现平局。但抛开这些人间的麻烦，数学本身是站得住的。素性检验是另一个经典例子。费马小定理指出：若 n 是素数，那么对 0 到 n-1 之间的任意 a，a 的 n-1 次方对 n 取模后都回到 a。只要有一次不成立，n 就不是素数。随机选取的一批 a 全部通过，则 n 很可能是素数。Miller–Rabin 检验因为存在伪素数，需要更加谨慎，但基本思路就是这个恒等式。

Karp 用同样的抽样思路，计算一组公式中至少满足其中一个公式的解有多少个。直接数会重复计算那些同时满足多个公式的解。可以把它想成一个 0/1 矩阵：每一行是一个公式，每一列是一个解，若某个解满足某个公式，对应位置就是 1。目标是数出至少含有一个 1 的列。抽样时，每一行被抽中的概率与其中 1 的个数成正比。抽中一行后，在该行中选一个 1，再看它所在的列，只有当这一行是该列中最早出现这个 1 的那一行时，才把这一列计入。这样每列只计一次，得到的估计在统计上是稳健的。这里有一个更一般的道理：如果某种现象几乎总是出现，那么随机抽样很可能会碰到它。代数恒等式检验也用的是同一招：两个公式表面上不同，就代入一个随机值。如果它们并不恒等，就会在很多点上结果不一致，所以随机选取的一个点就能把这种不一致显示出来。

到目前为止讲的都是最坏情况分析：无论输入是什么，算法都必须在这么多步内完成。Karp 的看法很明确：如果最坏情况分析表明一个算法总是好的，那就很好；如果它只表明解并不总是好的，就得退一步，问一问还能多常得到一个好的解。Fridman 说，人们一旦看到最坏情况很糟，就往往把算法扔进垃圾桶。Karp 说，这很可惜。SAT 是 NP 完全的，理论上不应该有高效算法。但在实践中，SAT 求解器能相当可靠地处理来自数字电路设计和程序正确性验证的、包含数百万个变量的实例。这些领域的人往往把可满足性看作一个简单的问题，他们并不需要了解它的理论地位。他们实际写下的那些实例，出于尚未完全弄清的原因，并不是那些难的实例。

旅行商问题是 NP 难的。人们借助整数规划求解器和一些数学技巧，把城市看作平面上的点，对几何实例求解，并证明了最优性，城市数量可达数万。这样的规模需要数个机器月的计算。一两千座城市则很快就能算完，而且最优性是经过证明的，并非启发式的猜测。我们并不相信存在多项式时间算法，但这些程序却跑得飞快。那么，有没有一种系统的方式来说明“实践中效果相当不错”？平均情况分析需要一个概率空间，以及“典型实例”的概念，而这非常困难。在完成 NP 完全性方面的研究之后，Karp 想为组合算法找些积极的结论。他选择了一条省事的路：采用过于简单化的假设。生成随机图的方法是不断加入随机的边，直到边数足够为止。在这种模型下，他和其他人证明了一些漂亮的结果。哈密顿回路（Hamiltonian cycle），即恰好经过每个顶点一次的回路，在边数略多于 n log n 时，很可能存在，并且有一种启发式算法能以高概率找到它。

这一圈人沿这条路线做出了很多成果，那是一个很好的游乐场。不过整个领域的反应并不热烈，因为假设过于简单。过了一段时间，他得出结论：这些结果对实际应用的意义不大，都是玩具问题。Fridman 问，能否做到机器学习最好时的那种状态：一个真实的数据集，一个公开的排行榜。Karp 说，基本做不到。Knuth 收集过一批种类繁多的图，让人能观察算法在不同类型的图上的表现，但要定义自己真正关心的那类图，本身就已经不是件简单的事。对于图和网络上的组合问题，并不存在与监督学习的训练集相对应的东西。理论计算机科学中一个以实证为基础的分支——比如取 Facebook 之类社交网络的子图，并证明出理论界会认可的结论——至今还没有形成。确实有一个叫作实验算法学的领域：研究者拿到一组样例，或者随机生成一组，然后报告运行表现。但至于这些样本能否代表什么，目前并没有令人信服的证据。

在一些开放问题中，Karp 提到了他与 Richard Lipton 在 1979 年发表的一篇论文。取一个固定规模的 NP 问题，比如 52 个城市的旅行商问题，然后问：是否存在一个专门针对该规模的小型布尔电路，输入是图的边，输出是“是”或“否”，表示是否存在长度为 L 的巡回路线。如果 P 等于 NP，这些问题都有多项式规模的电路。更值得追问的是反方向：一个问题能否在每个规模上都有一个小电路，这些电路彼此之间可以毫无关联，却不存在一个对所有规模都适用的统一多项式时间算法？他们证明，如果 NP 有小电路，那么多项式层级就会坍缩到第二层。第一层是 P。第二层是 NP：存在某个 X，使得某种性质成立。第三层是：对所有 X，都存在某个 Y。这有点像博弈论中的结构：对第一个参与者的每一种策略，第二个参与者都有应对。更高的层级会叠加更多量词。如果 NP 有小电路，那么三个量词、四个量词，乃至任意多个量词，都无济于事。这是证据，并非证明；而且这个证据本身很奇怪，它等于说：这件事太离奇，所以不会发生。P 不等于 NP 已经够离奇的了。无论哪种情况，都得去与那条龙较量。

Karp 说，机器学习属于另一个世界。它的成果大多是经验性的，更接近 SAT 求解器：人们观察到，在实际中出现的公式上，求解器的表现不错。它的成功是真实的，图像处理、机器人、语言、博弈等领域都有突破。一个副作用是，在这个领域拥有名声，要成为百万富翁就不太难，因为各家公司都相信 AI 能解决各种问题。它的局限同样真实。卷积网络在训练集之外的泛化能力好得惊人，而我们对此并没有理论上的理解。这些网络很难被理解，几乎得不出什么洞见。你可以判断一张照片是否属于另一组样本，却无法刻画区分各类物体的特征。Fridman 指出，神经网络在某种意义上正是他们刚才讨论的那种小电路。Karp 说，从某种意义上是这样，随后又加以修正：它是一种算法，一个可计算的函数，给它输入，就得到输出。它缺少的是那种可以读出结构的、算法式的输入操作。物体的边缘不会从电路中自然浮现。Fridman 说，电路对此是清楚的，只是我们看不清，就像大脑对它自己也不清楚那样。Karp 认可这一点，同时补充说，在视觉和听觉方面我们确实有一些原理，但在更深的认知任务上，我们并没有。

生物信息学仍然让他惊叹，尤其是人们已经开始能够编辑 DNA：取一段序列，在基因组中找到它，然后对它做些什么。这是把生物系统带入算法世界的一步。它同时也带来伦理问题。编辑一个个体，与编辑生殖细胞不是一回事，后者会影响所有后代。即便针对个体，也存在一种傲慢：你假设敲除某个基因是有益的，却并不知道副作用。农业和医学可能获益良多，而伦理问题会始终摆在桌面上。从算法的角度，可以分析基因组数据：哪些基因在细胞中起作用、在什么条件下起作用，哪些蛋白质彼此影响，哪些蛋白质存在直接的物理接触，以及如何对它们测序和修改。这是一个统计性的大数据问题，因此属于计算机科学。数据集正在不断增长，相关的应用还包括祖源追溯、疾病易感性评估，以及针对个人基因组的定制化治疗，例如对一位女性来说，乳腺癌的易感倾向是否强到需要采取行动，也属于这类问题。

Karp 把自己 1985 年的图灵奖演讲，献给了父亲的记忆。他记得最清楚的画面，是父亲站在黑板前徒手画圆，吸引住一群各色各样的八年级学生。Karp 有时能悄悄溜进教室去听。父亲在讲台上最为出彩：整个人仿佛活了过来，又讲又聊，和学生打成一片。Karp 从父亲身上承下的，是一份对教学的热切渴望。父亲退休不久，昔日的学生陆续来访：有人跟他一起做过研究，有人看过他写的文章，有人选过他的课。他们没有提 1979 年那篇论文，也没有提 1992 年那篇。他们说起的，是从课堂上带走的东西：思路与讲课的方式，而非具体的细节。

在伯克利任教的早年，他备课堪称典范，总是准备得非常充分，因此能够根据课堂上发生的情况灵活变通。他给其他老师的前三条建议都是：准备，准备，再准备。充分的准备让你能从容应对随时出现的情况：如果一种讲法没有讲通，你可以换一种方式；学生提出问题，你也能应付。你能感受到教室里的气氛，看到学生的眼神和疑问，正因为准备充分，你才能游刃有余。让学生爱上计算机科学的那个顿悟时刻，每个人都不一样。有的学生其实已经自己跑起来了，只需要有人听他讲讲；有的需要推一把；有的则需要被劝着去合作，不要一个人闷头干。每个学生都有起伏，要把每个人当作一个有血有肉的人来对待，帮他激发出最好的状态。人是很复杂的。

如果能重温家人之外的某个时刻，他会选择那段时间：一个懒散的本科生，在研究生第一年仍然很懒散，却开始做研究了。几份暑期工作让他能够做出贡献，也有了自己的想法。后来他修了一门数学方法与运筹学的课，囫囵吞枣般地消化了全部内容，分数比其他人高出 20 分，因此引起了系里老师的注意。这让他意识到自己有一定的能力，也意识到自己正朝着某个方向前进。Fridman 最后引用了 Isaac Asimov 的一句话：“我不害怕计算机，我害怕的是没有计算机。”Karp 在整场两个小时的访谈中，态度比这句话要平静得多。他不害怕计算机，也不认为计算机会很快超过我们。他更感兴趣的，是看到某样东西有效，与真正理解它为什么有效，两者之间的那段距离。