以下是与理查德·卡普的对话，他是加州大学伯克利分校的教授，也是理论计算机科学史上最重要的人物之一。1985年，他因在算法理论方面的研究获得了图灵奖，其中包括用于解决网络最大流问题的Admirable Carp算法的开发，用于在二分图中查找最大基数匹配的Hopcroft-Karp算法，以及他关于复杂性理论的里程碑式论文《组合问题中的可归约性》，他在其中证明了21个问题是NP完全的。这篇论文可能是引爆人们对NP完备性研究和P与NP问题普遍兴趣的最重要催化剂。

广告的快速摘要，有两个赞助商：Eight Sleep床垫和Cash App。请考虑通过访问asleep.com/lex并下载Cash App并使用代码LEXPODCAST来支持这个播客。点击链接购买商品，这是支持这个播客的最佳方式。如果你喜欢这个节目，请在YouTube上订阅，在Apple Podcast上给它打5星好评，在Patreon上支持它，或者在Twitter上与我联系@lexfriedman。像往常一样，我会先进行几分钟的广告，中间绝不会有广告打断对话的流畅性。

本节目由Eight Sleep及其Pod Pro床垫赞助，您可以在asleep.com/lex上查看，可享受200美元的折扣。它可以通过应用程序控制温度，可以冷却到55华氏度，并且床的每一侧都可以单独控制。研究表明，温度对我们的睡眠质量有很大影响。就我个人而言，它改变了我的生活，我非常喜欢它。现在已经几周了，我真的很享受它，一方面是因为我睡得更好了，另一方面它本质上是一张智能床垫。我有点想象这是人工智能的早期阶段，它将成为我们生活中方方面面的组成部分，而将人工智能融入生活中最重要的方面之一——睡眠，我认为它具有很大的潜力，能够带来益处。Pod Pro床垫装满了传感器，可以跟踪心率、心率变异性和呼吸频率，并在其应用程序中显示所有这些数据。应用程序的健康指标非常棒，但仅就冷却功能而言，它就值回票价了。我不是总能睡着，但当我睡着时，我选择Eight Sleep Pod Pro床垫。请访问8sleep.com/lex查看，可享受200美元的折扣，并记住，仅仅访问网站并考虑购买就能帮助说服Eight Sleep的各位，这个愚蠢的老播客值得他们未来赞助。

本节目还由伟大的、强大的Cash App呈现，它是App Store中的第一金融应用。下载后，使用代码LEXPODCAST。Cash App可以让你向朋友汇款，购买比特币，并用低至1美元的资金投资股票市场。它是我用过的最好的应用程序界面之一。对我来说，好的设计就是一切都简单自然；坏的设计就是应用程序碍事，要么是因为它有bug，要么是因为它试图过度提供帮助——我指的是你，微软的Clippy。虽然我仍然爱你。我的大脑和心灵中有一大部分热爱设计事物，也热爱欣赏他人的伟大设计。所以，再次强调，如果你从App Store或Google Play下载Cash App并使用代码LEXPODCAST，你将获得10美元，Cash App还将向First捐赠10美元，这是一个致力于在全球范围内推动青少年机器人和STEM教育的组织。

现在，是时候与理查德·卡普进行对话了。

你写道，13岁时你第一次接触到平面几何，并被形式证明的力量和优雅所震撼。从那时起，你还记得有什么平面几何中的问题、证明、性质或想法让你着迷，或者让你享受去证明各种方面的吗？

迈克尔·拉宾给我讲了一个故事，关于他年轻时的一次经历。他因为行为不端被赶出教室，在学校走廊里闲逛，偶然遇到了两个正在研究“找出两个不重叠圆之间最短距离”问题的年龄较大的学生。迈克尔想了想，说：“你取两圆圆心之间的直线，而两圆之间的线段就是最短的，因为直线是两圆圆心之间最短的距离，而连接两圆的任何其他线都会更长。” 我想了想，他也想了想，我同意，这真是太优雅了，纯粹的推理就能得出这样的结果。当然，两圆圆心之间的最短距离就是一条直线。

你能再说一遍，那个证明的下一步是什么？

任何连接两圆的线段，如果你通过每边取半径来延长它，你就会得到一个有三条边的线段，它连接了两圆圆心。这条线段的长度至少要等于最短路径，也就是直线。

是的，直线。哇。是的，这确实非常简单。

那么，是什么让你觉得这种优雅如此引人入胜呢？

仅仅是你可以通过纯粹的推理，毫无争议地确立几何学中的一个事实。我也很享受在平面几何中解决谜题的挑战。这比早期的数学课程有趣得多，那些课程主要涉及算术运算和对它们的操纵。

几何学本身有什么吸引你的地方吗？它略带视觉的成分？

是的，绝对。尽管我缺乏三维视觉，我并不擅长三维视觉。

你是说能够想象三维物体？

三维物体，或者……曲面、超平面等等。所以，在那里我没有直觉。但例如，三角形内角和为180度的证明非常有说服力，而且令人惊讶的是，这竟然可以做到。

为什么这令人惊讶？

嗯，这是一个令人惊讶的想法，我想。为什么证明起来很困难？不是的，关键在于它如此简单，但又如此令人信服。

你还记得那个证明三角形内角和为180度的证明吗？

你从一个角开始，画一条与对边平行的线。这条线将另外两条边之间的角度分成三等份，你得到一个半平面，它必须加起来等于180度，并且它由角度组成。通过……交错角的相等性，你得到了三角形边与三角形三个角之间的一种对应关系。

几何学对你未来研究组合算法有什么影响吗？它是否在某种程度上产生了影响，让你能够……那些最初如此吸引你的谜题和视觉方面？

欧几里得几何学尤其没有。我认为我经常使用线性规划和整数规划等工具，但那些需要高维可视化，所以我倾向于通过代数性质来理解。

是的，你通过代数，线性代数，而不是通过可视化。

嗯，例如在寻找多面体最高点方面的解释，就像线性规划一样，是有启发性的。但同样，我没有那种特别能给我启示的高维直觉，所以我倾向于依赖代数。

那么，为了详细说明这一点，当你思考算法，或者任何数学问题时，你喜欢进行什么样的可视化？

嗯，我认为通常一个算法涉及对某个内部循环的重复。所以我可以想象……到期望解决方案的距离如何随着迭代而减小，直到你最终达到精确解决方案，并尝试采取让你更接近……尝试采取让你更接近的步骤，并有收敛的确定性。所以，它基本上是……算法的机制通常非常简单，尤其是当你尝试在计算机上进行一些操作时。例如，我做了一些关于旅行商问题的工作，我可以看到有一个特定的函数需要最小化，而看到 successive approaches to the minimum to the optimum 真是太迷人了。

你是说旅行商问题，你必须访问……

是的，每个城市，一次都不漏。

是的，就是这样。找到穿过城市的最短路径。

是的，这是一个典型的、标准的、非常好的问题，而且非常难，对吧？

正是如此。

你能再说一遍，关于目标函数，能够思考目标函数并最大化或最小化它，有什么好处呢？

嗯，就是……随着算法的进行，你正在取得持续的进展，并最终达到最优值。所以，也许有两个部分，也许你可以纠正我，但首先是关于解决方案会是什么样子的直觉，甚至可能想出一个解决方案。第二是证明这个东西实际上会非常好。对你来说，哪个部分更难？魔法发生在第一个直觉阶段，还是发生在实际展示它将达到精确解决方案并以特定复杂度运行的混乱细节中？

魔法在于，最优值与当前值之间的差距单调递减，你可以看到它正在发生，并且……各种衡量正在发生的事情的指标都在不断改进，直到最终达到最优值。也许稍后我们会谈论分配问题，我可以更好地说明。

现在，再次放大视角。正如你所写，唐纳德·克努斯曾引起人们对一类人——他们从思考计算过程的结构中获得极大的审美愉悦——的注意。唐纳德称这些人是“极客”，而你写道，你记得你意识到自己就是这样一个人。你被展示了解决分配问题的匈牙利算法，对吧？所以，也许你可以解释一下分配问题是什么，以及匈牙利算法是什么。

在分配问题中，你有 N 个男孩和 N 个女孩，并且你知道匹配第 i 个男孩和第 j 个女孩的吸引力或成本。对于所有 i 和 j，你都有一个数字矩阵，你想找到一种一对一的匹配方式，使得相关成本的总和最小化。所以，这是将男孩与女孩匹配的最佳方式，或者男人与工作，或者任何两组……

任何可能的匹配都是可能的吗？或者……

所有一对一的对应都是允许的。如果存在不允许的连接，那么你可以认为它的成本是无限的。

所以，你所做的是……取决于一个观察，即最优分配的身份，或者我们称之为最优排列，在从矩阵的任何行或列中减去一个常数时不会改变。你可以看到不同分配之间的比较不会因此而改变，因为你……如果你将某一行或某一列的所有元素都减去某个常数，所有解决方案都会减少该常数，减少的量等于该常数。所以，算法的思路是，从一个非负数矩阵开始，不断地从行或整个列中减去，同时保持……所有元素都是非负数的性质。

简单。是的。所以……所以，你必须做的是……找到小的移动，通过从行或列中减去常数来降低总成本。并且有一种特定的方法可以做到这一点，通过计算矩阵中元素的某种最短路径。你就这样一直进行下去，直到你最终得到一个完整的零排列，而矩阵是非负的，然后你就知道那是成本最低的。

这听起来有那么简单吗？矩阵中的最短路径部分？

简单之处在于如何找到……我稍微简化了一下。你最终会从某些行或列中减去一个常数，并将相同的常数加回到其他行或列，以免……不会减少任何零元素，保持不变。但每个单独的步骤都会修改几个行和列相同的数量，但总体上会降低成本。

所以，这种优雅让你觉得“啊哈，这太美了！”？

是的，这太神奇了，像这样简单的事情可以解决像这样的问题。是的，这真的很酷。如果我有机械能力，我可能会喜欢做木工或其他活动，在那里你将某物塑造成美丽而有序的东西。而这种有序、系统的性质……那种创新的算法让我感到愉悦。

你对唐纳德·克努斯所说的“极客”这个概念怎么看？你认为这是一种特殊的思维方式，让你能够发现计算过程中的优雅，还是我们所有人都能发现这种美？你是天生的吗？

我认为是的。我一直喜欢玩数字。我过去常常通过在脑海中乘以四位小数来娱乐自己，然后通过从一开始就加倍数字来入睡，只要我能做到。测试我的记忆力，我保留信息的能力。

我还在某处读到，你写道，你喜欢通过……我记得是乘以四位数的数字来向朋友炫耀。

是的，一对四位数的数字。

我曾在波士顿郊外的一个海滩度假村打过暑期工。我当时是……我是一个……

我当时是……我是一个……

我.

暂停一下，那是你尝试做的第一个问题映射之一，映射有多难？你说展示起来不难，但你知道这是一个巨大的飞跃，确实是一个巨大的飞跃。嗯，让我给你另一个例子，NP 中的另一个问题是图是否包含给定大小的团。现在的问题是，我们能否将命题逻辑问题归约到是否存在特定大小的团的问题？嗯，如果你看看命题逻辑问题，它可以表示为若干个子句，每个子句的形式都是 A 或 B 或 C，其中 A 是问题中的一个变量或一个变量的否定，而命题逻辑问题的一个实例可以使用布尔逻辑运算重写，可以重写为子句集合的合取，即一组“或”的“与”，其中每个子句是变量或否定变量的析取（“或”）。所以，可满足性问题的满足性问题的意思是，那些子句是否可以同时满足。现在，要满足所有这些子句，你必须在每个子句中找到一个将要为真的项，在你的真值指派中将要为真，但你不能同时使同一个变量为真和为假。所以，如果你在一个子句中有变量 A，并且你想通过使 A 为真来满足该子句，你也不能在其他某个子句中使 A 的补集为真。所以目标是使每个子句都为真，如果可能的话，使其满足。使其为真的方法是，子句中的至少一个项必须为真。所以，现在我们，将这个问题转换为所谓的独立集问题，你只是在询问图中的一组顶点，使得其中没有两个顶点是相邻的，有点像是团问题的反面。所以我们已经看到，我们现在可以将其表示为找到一组项，每个子句一个，而不选择变量及其否定，因为如果你给变量分配了真值，那么否定变量必须具有相反的真值，对吧？因此，我们可以构建一个图，其中顶点是所有子句中的项，并且如果两个项之间存在边，则它们都位于同一个子句中，因为你只选择每个子句中的一个元素，并且如果它们代表同一个变量的相反值，因为你不能使一个变量同时为真和为假。因此，你得到一个图，其中有所有这些变量的出现，有边，这些边意味着你不能同时选择边的两端，因为它们在同一个子句中，或者它们是彼此的否定。好了，这首先是，从宏观上看，这是一个非常强大的想法，你可以将图与逻辑方程联系起来，以某种方式，并为图上某个特定问题的所有可能表述进行映射。是的，我仍然难以相信这是可能的，就是说，你如何看待它，就是说，如此多的问题如此紧密地联系在一起，它们都类似于组合算法，它们都以某种方式相关。是的，我知道这可以被证明，但你如何看待它，就是说，这是真的？嗯，如果它们具有相同的表达能力，你就可以取其中任何一个，并将其翻译成另一个的术语。你知道，它们具有相同的表达能力也意味着它们可以相互翻译。而我在 1971 年的论文中，我选择了 21 个基本问题，常见的组合问题，如打包、覆盖、匹配等，它们都属于 NP 类，并表明可满足性问题可以重新表述为其中任何一个，其中任何一个都具有相同的表达能力。所以，这就像是宣战，说可能还有更多这样的问题，对吧？但这只是说，看，它们都一样，它们都一样，但又不完全一样。是的，是的，它们在表达任何其他问题的丰富性方面都一样，但这并不意味着它们具有相同的计算复杂性。但我们可以说，要么所有这些问题，要么没有一个问题可以在多项式时间内解决。那么 NP 完全和 NP 难类在哪里呢？那只是一个小小的技术细节。所以，当我们谈论决策问题时，这意味着答案只是“是”或“否”。存在一个大小为 15 的团，或者不存在一个大小为 15 的团。另一方面，优化问题是问“找到最大的团”。答案不是“是”或“否”，而是 15。所以，当你要求，当你对不同的解决方案进行估值，并要求具有最高估值的那个时，这是一个优化问题，这两种问题之间有非常密切的亲缘关系。但作为最难的决策问题，最难的“是-否”问题的对应项，是最小化或最大化目标函数。所以，在优化方面，在 NP 类中最难的问题被称为 NP-hard，而不是 NP-complete。NP-complete 是用于决策问题的，NP-complete 是用于决策问题的。所以，如果有人证明 P=NP，你认为那个证明会是什么样的？如果你自己来设想，如果可能的话，证明或者演示一个算法。我只能说，它将涉及我们现在没有的概念和我们现在没有的方法。你认为这些概念存在于复杂性理论内部，存在于算法的计算分析内部吗？你认为有一些完全出乎意料的概念是我们还没有考虑到的吗？我认为，如果存在证明 P=NP 或 P≠NP 的话，它将依赖于现在出乎意料的概念。现在，如果证明了这一点，无论是哪种情况，P=NP 或 P≠NP，实际上 P=NP，它会对理论计算机科学和软件系统产生什么影响？嗯，我认为它会对世界产生巨大的影响，无论哪种情况。如果 P≠NP，这是我们所期望的，那么我们就知道，对于我们遇到的绝大多数组合问题，因为它们已知是 NP 完全的，我们就无法通过高效的算法来解决它们。然而，有一点点希望，我们也许可以解决大多数实例。我们所知道的是，如果一个问题不在 P 中，那么它就不能在所有实例上有效地解决。但是，基本上，它将，它将，如果我们发现 P≠NP，这意味着我们不能总是期望得到这些问题的最优解，我们必须依赖于可能大部分时间有效的启发式方法，或者给我们近似的良好解决方案，但不是。所以，我们会带着更多的接受和舒适的目光转向启发式方法。正是如此。好的，那么让我问一个浪漫化的问题，在你看来，你一生中或该领域中最美丽的组合算法是什么？或者你遇到的，或者你自己开发的？哦，我非常喜欢稳定匹配问题，或者稳定婚姻问题。稳定匹配问题是什么？想象一下，你想让 N 个男孩和 N 个女孩结婚。每个男孩都有一个按顺序排列的女孩名单，他的第一个选择是他第 N 个选择，而每个女孩也有一个男孩的顺序名单，她的第一个选择，第二个选择，等等。我们将说，男孩和女孩的一对一匹配是稳定的，如果匹配中没有两个夫妇，使得第一对夫妇中的男孩比第二对夫妇中的女孩更喜欢她而不是她的伴侣，并且她也喜欢她而不是她现在的伴侣。换句话说，如果匹配是稳定的，那么就没有一对夫妇想私奔，留下他们的伴侣。天哪，是的，这实际上与匹配居民和医院以及其他一些现实生活中的问题有关，尽管形式与我描述的略有不同。所以，事实证明，对于任何一组偏好，都存在一个稳定的匹配，而且，它可以通过一个简单的算法来计算，其中每个男孩开始向女孩提出求婚，如果女孩收到求婚，她就暂时接受，但如果她能得到更好的求婚，她可以稍后放弃。男孩们开始按照他们的名单，向他们的第一、第二、第三选择提出求婚，直到停止，当一个求婚被接受时。但与此同时，女孩们正在观察她们收到的求婚，如果她得到更好的求婚，女孩就会放弃她现在的伴侣，而男孩们永远不会回头，他们永远不会回头。是的，所以一旦他们被拒绝，他们就不会再尝试了，他们不会再尝试了，因为女孩们随着她们收到越来越好的求婚，她们的地位总是在提高，男孩们则沿着他们的名单往下走，从他们最喜欢的开始。而且，人们可以证明，这个过程会结束，每个人都会找到匹配，而且你不会有任何一对夫妇想逃跑。你觉得证明本身或者算法本身很美，还是说，简单地基于两个匹配的底层规则，算法的简单性是美丽的部分？两者我都认为如此。而且你还有这样的观察，你可能会问，谁更好，是那些提出求婚的男孩，还是那些对求婚做出反应的女孩？事实证明，是那些男孩做得最好，也就是说，每个男孩的境况至少和他能在任何其他稳定匹配中做得一样好。所以，对男孩们来说，有一个教训，你应该出去，积极主动，提出那些求婚，放手一搏。我不知道这是否能直接在哲学上映射到我们的社会，但它肯定是一个引人注目的概念，而且正如你所说，很可能有很多实际的现实世界问题可以映射到这一点。是的，嗯，你遇到了并发症，例如，当丈夫和妻子想被分配到同一家医院时会发生什么？所以你必须考虑到这些约束，然后问题就变成了 NP-hard。或者，为什么丈夫和妻子被分配到同一家医院是个问题？不，这是可取的，所以是可取的，或者至少去同一个城市。所以，如果你，我认为，如果你将居民分配给医院，然后你对医院有一些偏好，居民有他们自己的偏好，男性和女性居民都有他们自己的偏好，医院有他们的偏好，但是，如果居民 A，那个男孩要去费城，那么你也希望他的妻子也被分配到费城的一家医院。那么，是什么步骤使它成为一个 A 和 B 的难题？你提到你有一个额外的约束，那就是不仅仅是个人的偏好，而是婚姻的双方必须被分配到同一个地方。我有点迟钝，所谓的完美匹配，不是稳定匹配，你指的是什么？那是当两个伴侣试图……好的，让你困惑的是，在问题的第一个解释中，我让男孩和女孩匹配。是的，在第二个解释中，你让人类和机构匹配。而且人类之间存在耦合。在人类内部，任何额外的微小约束都会使其成为一个 NP-hard 问题。嗯，是的，好吧。顺便说一句，你提到的算法不是你的吗？不，不，那是盖尔和夏普利的。我的朋友大卫·盖尔在他获得诺贝尔奖的一部分之前就去世了，但他的搭档夏普利与另一位经济学家分享了诺贝尔奖，因为他的人类，因为经济学，因为源于稳定匹配思想的观点。所以，你也自己开发了一些优雅、美丽的算法，再次选择你的孩子。罗宾·卡普算法用于字符串搜索模式匹配，阿德明·卡普算法用于最大流，我们提到了霍普克罗夫特·卡普算法用于在二分图中找到最大基数匹配。有没有让你特别自豪的算法，无论是美丽、优雅，还是仅仅是你生命中恰当的发现和发展？我喜欢拉文·卡普算法，因为它说明了随机化的力量。问题是决定一个由某个字母表组成的符号组成的给定长字符串是否包含一个给定的单词，一个特定的单词是否出现在一个非常长的单词中。所以，算法的想法是将我们正在寻找的单词与一个指纹相关联，一些数字或一些组合对象来描述那个单词，然后当你沿着更长的单词滑动时，寻找那个相同指纹的出现。我们所做的是将一个数字与每个单词相关联，所以我们首先想到出现在单词中的字母是数字的数字，比如说十进制，或者无论有多少种不同的符号，那就是数字的基数。是的，所以每个单词都可以被认为是一个数字，字母是那个数字的数字。然后我们选择一个特定范围内的随机素数，我们将那个单词视为一个数字，然后除以那个素数取余数。所以，想出一个好的哈希函数，它是一种哈希函数，是的，它为你提供了那个特定单词的一个小捷径。所以，这是，这是，它与我们试图进行字符串匹配的其他算法非常不同，其他算法通常是组合的，并且不涉及采用随机指纹的想法。是的，而且指纹识别有两个优点：一个是我们沿着长单词逐位滑动时，我们保持一个特定大小的窗口，我们正在寻找的单词的大小，我们计算那个长度的每个片段的指纹，而且事实证明，只需要几次算术运算就可以从一个片段的指纹到当你滑动一个位置时得到的指纹。所以，所有指纹的计算都很简单，其次，如果素数是从某个范围随机选择的，那么你不太可能得到两个有问题的片段具有相同的指纹。是的，所以有一个小的错误概率，事后可以检查，而且计算也很容易，因为你使用的是这些模某个大素数的余数。所以，随机算法的魔力在于，如果你加入一点点随机性，它就能让你采用一个非常朴素的方法，一个看起来很简单的方法，并且运行得非常好。那么，你能否退一步说，什么是随机算法，这个算法类别呢？它只是能够从某个范围中抽取一个随机数，或者将一个随机数与某个对象相关联，或者从某个集合中随机抽取。另一个非常简单的例子是，如果我们进行总统选举，并且原则上我们想选出获胜者，我们可以抽取一个全国所有选民的随机样本，如果样本足够大，比如几千人，那么该群体中最受欢迎的候选人很可能就是正确选择，这将通过计算数百万张选票得出。当然，我们不能这样做，因为首先，每个人都必须觉得自己的选票被计算在内，其次，我们不能真正从那个群体中进行纯粹的随机抽样。而且，我猜第三，可能会出现平局，在这种情况下，我们不会在两个候选人之间有显著的差异。但撇开这些不谈，如果你没有所有这些人类的混乱，你可以证明那种随机选择将是，那种随机选择将，将以非常低的错误概率解决问题。另一个例子是测试一个数字是否是素数。所以，如果我想测试 17 是否是素数，我可以选取 1 到 17 之间的任何数字，将其提高到 16 次方模 17，你应该得到原始数字。这是一个著名的费马公式，关于它被称为费马小定理，如果你取 0 到 n-1 范围内的任何数字 a，并将其提高到 n-1 次方模 n，如果数字是素数，你将得到数字 a。是的，所以如果你没有得到数字 a，那就是一个证明该数字不是素数的证明。而且，你可以证明，经过适当定义，你得到一个不等于 a 的值的概率，违反费马结果的概率非常高。所以，这提供了一种快速证明一个数字不是素数的方法。它比这稍微复杂一些，因为存在某些 n 的值，需要做一些更复杂的处理，但这基本思想是利用一个对素数成立的恒等式，因此，如果它在任何非素数实例上失败，你就知道该数字不是素数。这是一个快速的、快速的证明一个数字不是素数的方法。你能否更详细地解释一下，你直觉上为什么随机性如此有效，并产生如此简单的算法？嗯，在理论上可以进行选举的例子，你可以抽取一个样本，并依赖于样本的有效性来真正代表整体，这是统计学的基本事实，它提供了很多机会。我实际上利用了那种随机抽样思想来设计一个算法，用于计算满足特定命题逻辑公式的解的数量。所以，可满足性问题的一个版本，或者可满足性问题的一个版本。有没有什么有趣的见解你想详细说明，比如那个算法的某个方面可能有助于描述？所以，你有一个公式集合，你想计算满足至少一个公式的解的数量。你可以计算满足任何一个公式的解的数量，但你必须考虑到，如果一个解解决了多个公式，它可能会被计算多次。所以，你所做的是根据满足每个单独公式的解的数量来抽样公式。这样，你就可以得到一个随机解，然后通过查看满足那个随机解的公式数量来纠正，并且不重复计数。所以，你可以这样想：你有一个零和一的矩阵，你想知道有多少列包含至少一个一。你可以计算每一行有多少个一。所以，你可以根据一的数量从行中抽取，如果一行有一个以上的一，它就会更频繁地被抽取。但是，如果你从那一行抽取，你必须沿着列往上走，看看同一个一在不同行中重复出现的位置，并且只将其计为成功或命中，如果它是包含那个一的最早的行。这就给你提供了一个对包含至少一个一的列的总数的稳健的统计估计。所以，这是一个与研究随机抽样相同的原理的例子。另一种观点是，如果你有一个几乎总是发生的现象，那么如果你抽取一个发生的场合，你很可能，而且你正在寻找一个随机发生的场合，它很可能会奏效。这在解决恒等式，解决代数恒等式时会出现。你得到两个可能看起来非常不同的公式，你想知道它们是否真的相同。你可以做的是随机选择一个值，并在该值处评估这两个公式，看看它们是否一致。你依赖于这样一个事实：如果公式不同，它们就会有很大的分歧，因此随机选择很可能会显示出分歧。如果有多种方式使两者产生分歧，而你只需要找到一种分歧，那么随机选择很可能会产生它。总的来说，我们刚刚讨论了随机算法，但我们可以看看算法的概率分析，这给了我们一个机会退一步，正如我们所说，我们一直在谈论的是最坏情况分析。你能否评论一下最坏情况分析与最佳情况分析、平均情况概率分析的有用性和力量？我们如何看待理论计算机科学的未来，以及我们对算法进行的分析？最坏情况分析是否仍然占有重要地位，还是我们想朝着平均情况分析迈进？是的，那里的挑战是什么？所以，如果最坏情况分析表明一个算法总是好的，那没关系。如果最坏情况分析被用来表明解决方案不总是好的，那么你必须退一步做些别的事情，问问你多久能得到一个好的解决方案。只是停顿一下，那太美了，因为我认为我们倾向于评判算法，一旦它们的“最坏情况”被证明很糟糕，我们就把它们扔进垃圾桶。是的，而且那很不幸。我认为一个很好的例子是，回到可满足性问题。有非常强大的程序称为 SAT 求解器，实际上在实践中相当可靠地解决了数百万变量的实例，这些实例出现在数字设计或程序改进等应用中。所以，在许多应用领域，尽管可满足性正如我们已经讨论过的，是 NP 完全的，SAT 求解器运行得如此之好，以至于该学科的人们倾向于认为可满足性是一个简单的问题。换句话说，出于我们不完全理解的原因，人们在设计数字电路或其他应用时形成的实例使得可满足性不难检查，甚至搜索一个令人满意的解决方案也可以在实践中有效地完成。而且有很多例子，例如我们讨论过的旅行推销员问题。所以，为了刷新我们的记忆，问题是，你有一组城市，城市之间有成对的距离，你想找到一条穿越所有城市的路线，使总成本最小化，所有遍历的边的总成本，所有城市之间的旅行。问题是 NP-hard，但人们使用整数规划代码以及一些其他数学技巧来解决平面中的城市等几何实例的问题，并获得具有数万个城市的问题的最优解。实际上，解决如此规模的问题需要几个月的计算机时间，但对于规模为一千或两千的问题，它会快速获得可证明的最优解，尽管我们知道旅行推销员问题不太可能在多项式时间内解决。是否有像严格的系统化方法这样的方法，你刚才说“在实践中”这个算法相当好？换句话说，平均情况分析，或者你还提到平均情况分析需要你了解典型情况，典型实例，而这可能非常困难。这非常困难。所以，在我最初关于证明所有这些问题都是 NP 完全的工作之后，我一直在寻找一种方法来为组合算法带来一些积极的光明。我试图做的是研究问题在平均情况下的行为，或者高概率下的行为。但我不得不对概率空间是什么，样本空间是什么，我们所说的典型问题是什么做一些假设。这很难说。所以我选择了最简单的方法，做了一些非常简化的假设。例如，我假设，如果我们用一定数量的顶点和边生成一个图，那么我们将通过一次随机选择一条边，直到我们得到正确的边数来生成图。这是一个已经被数学研究了很多的随机图模型。在这个模型中，我可以证明各种美妙的事情，我和其他人也在这方面工作。所以，我们可以确切地知道有多少条边才能存在一个所谓的哈密顿回路，这是一个访问每个顶点恰好一次的循环。我们知道，如果边数比 n log n（其中 n 是顶点数）多一点点，那么这样的循环很可能存在，我们可以给出一个启发式方法，它很可能找到它。我们在这个方向上得到了很多结果，但我工作的领域对接受这些结果的意义持相当冷淡的态度，因为我们对我们所处理的图的种类做出了如此简化的假设。所以，我们可以证明各种美妙的事情，这是一个很棒的游乐场，我喜欢做它，但过了一段时间，我得出结论，它在实际应用方面没有多大意义。哦，所以，它进入了玩具问题的世界，是的，可以，但好吧，那么，有没有办法找到好的、有代表性的、现实世界中有影响力的实例，来证明一个算法是好的？这有点像机器学习的世界，它尽力做的是找到一个现实世界的数据集，并展示性能。所有的会议都专注于在那个现实世界的数据集上击败性能。在复杂性分析中是否存在类似的现象？不完全是。唐·克努斯开始收集来自各种地方的图的例子。所以，他会有一大堆不同的图供他选择，他可以研究算法在不同类型图上的性能。但是，在那里，能够定义一个你感兴趣的图类非常重要和引人注目。似乎是一个非平凡的步骤，如果我们谈论的是现实世界中我们应该关心的实例。是的，那里没有类似监督学习训练集的东西，你知道，你假设世界给了你一些例子来处理。对于图和网络上的组合问题，我们并没有真正拥有那个。你知道，数据集的巨大增长，你认为理论计算机科学的某个方面，我可能在矛盾自己的问题，同时说它，会有一个经验方面，它将允许这些数据集如此庞大，我们将开始使用它们进行分析，就像，你知道，如果你想说一些关于图算法的事情，你可能会拿一个社交网络，比如 Facebook，看看它的子图，并证明一些关于 Facebook 图的东西，并在理论计算机科学界受到尊重，同时也在理论计算机科学界受到尊重。我担心，这还没有实现，是吗？是 P=NP 吗？这不可能吗？在理论计算机科学界，展示一些在现实世界数据集上的性能，是否真的不可能发表一篇成功的论文，或者这两个世界真的不同？我可以说，它们还没有真正融合。有一个实验算法学的领域，人们有时会得到一些例子，有时他们只是随机生成它们，并报告性能。但没有令人信服的证据表明样本代表任何东西。那么，让我们来谈谈突破和未解决的问题。对你来说，最引人注目的未解决问题是什么？在不久的将来，你看到了理论计算机科学的哪些可能突破？嗯，复杂性类之间存在各种各样的关系可以研究。我只是举一个例子，我在 1979 年与理查德·利普顿合写了一篇论文，我们在其中提出了以下问题：如果你取一个 NP 中的组合问题，比如说，然后你选择，你选择问题的大小，比如说它是旅行推销员问题，但大小为 52，然后你问，你是否可以得到一个高效的、小型布尔电路，为那个大小为 52 的问题量身定制，你可以将图的边作为布尔输入输入，然后得到一个长度为某个长度的路线的问题作为输出？换句话说，在这种情况下，你会简而言之地说，这个问题有小型电路，多项式大小的电路。现在我们知道，如果 P=NP，那么实际上这些问题将有小型电路。但反之呢？一个问题是否有小型电路，意味着一个为任何特定大小量身定制的算法可以工作得很好，但又不是一个多项式时间算法，也就是说，你不能将其写成一个对所有大小都好的单一统一算法？只是为了澄清，是针对特定大小的问题的小型电路，还是更进一步约束，是针对该大小的所有输入的，几乎是那个大小的，这是一个特定实例的平凡问题吗？所以，想出一个自动化的方法来构建电路，我想那会很难。但是，你知道，现在每个人都在谈论存在性的问题，存在的挑战。你可以问这个问题，哈密顿回路问题是否有针对每个大小的小型电路，换句话说，你可以根据大小量身定制解决方案，并获得多项式大小，即使 P≠NP，对吧？如果那是真的，那将是迷人的。我们证明的是，如果那是可能的，那么在复杂性理论中会发生一些奇怪的事情，某个级别，一个我可以简要描述的类，会发生一些奇怪的事情。所以，我将尝试描述我的意思。让我们开始吧。所以，我们必须定义这个层次结构，其中层次结构的第一级是 P，第二级是 NP。NP 是什么？NP 涉及形式为“存在某个东西，使得某个东西成立”的陈述。例如，存在一个着色，使得图可以用这么少的颜色着色，或者存在一个哈密顿回路，这是一个关于这个图的陈述。是的，所以，NP 处理这类陈述，即存在一个解决方案。现在，你可以想象一个更复杂的表达式，它说，“对于所有 x，存在一个 y，使得某个涉及 x 和 y 的命题成立”。那么，例如，在博弈论中，对于第一个玩家的所有策略，存在第二个玩家的一个策略，使得第一个玩家获胜，那就是层次结构的第二级。第三级将是“存在一个 a，使得对于所有 b，存在一个 c，使得某个东西成立”，你可以想象不断向上进入层次结构，你会期望复杂性类，对应于这些不同情况的类会越来越大，或者越来越难解决。而利普顿和我证明的是，如果 NP 有小型电路，那么这个层次结构将崩溃到第二级。换句话说，通过使你的表达式复杂化，用三个量词或四个量词或任何数量的量词，你不会获得任何额外的收益。我不确定那是什么意思。嗯，我认为这将是 NP 没有小型电路的证据，因为会发生一些非常奇怪的事情。但同样，这只是证据，不是证明。嗯，是的，这甚至不是证据，因为你说 P≠NP，因为必须发生一些奇怪的事情。我是说，这是，这是通过我们科学中缺乏怪诞来证明的，但似乎，似乎 P=NP 的概念本身就很怪诞。所以，无论你如何到达那里，你都必须在某个时候与龙搏斗。好吧，好吧，无论如何，这就是我们证明的。太棒了，所以，这是一个潜在的有趣未解决问题空间。让我问你关于另一个世界，机器学习，深度学习。你对机器学习领域的历史和当前进展有什么看法？它通常作为一个思想和人群的空间独立发展，而不是理论计算机科学或甚至计算机科学世界。是的，它与理论计算机科学世界非常不同，因为，是的，关于算法性能的结果往往是经验性的。它更类似于 SAT 求解器的世界，我们观察到，对于实际出现的公式，求解器运行良好。所以，它是那种类型，我们正在进入算法的经验评估。现在，很明显，在图像处理、机器人技术、自然语言处理方面取得了巨大的成功，游戏玩法是另一个方面，也取得了巨大的成功。其中一个影响是，如果你能在机器学习领域获得声誉，成为百万富翁并不难，而且会有各种各样的公司愿意给你提供月亮，因为他们认为，如果他们拥有 AI，他们就可以解决各种各样的问题。但也有局限性。一个是在监督学习问题中通过卷积神经网络获得的解决方案，即使对于训练集之外的输入，似乎也表现得惊人地好。但我们对为什么会这样没有理论上的理解。其次，你得到的解决方案，网络，非常难以理解，所以很少有见解。所以，是的，它们可能在你的训练集上运行良好，而且你也许能够发现你的照片是否出现在另一组输入中，但我们并不知道发生了什么。我们不知道区分照片或物体的特征，或者它们可能是什么，并不容易描述。嗯，这很有趣，因为你提到了想出一个小型电路来解决特定大小的问题。是的，神经网络在某种程度上就像小型电路。是的，但它们不是程序，就像你设计的那些是算法，程序一样，对吧？算法，神经网络不是。它们是算法，只是它们是，嗯，是的，这可能是一个语义问题，但它们不是一种算法式的输入操作。也许你可以争辩说，是的。嗯，它感觉更像是一个输入的函数，它是一个可计算函数，一旦你有了网络，你就可以在给定的输入上模拟它，并找出输出。但是，你知道，如果你想识别图像，那么你不知道图像的哪些特征实际上是，决定电路在做什么。电路是一种非常复杂的东西，而且，你知道，不清楚，你正在寻找的简单特征，物体的边缘或任何它们可能是，它们并没有从电路的结构中涌现出来。嗯，不清楚我们，但对电路来说是清楚的。嗯，是的，我的意思是，它不清楚，嗯，大象如何看待人脑，但对我们人类来说是清楚的，我们可以向彼此解释我们的推理，这就是认知科学，心理学领域存在的原因。也许，被解释给人听这件事有点被高估了。嗯，也许吧。我猜，你可以对我们的大脑说同样的话，当我们进行认知活动时，我们不知道我们是如何做的，真的。我们知道，至少对于视觉系统、听觉系统等等，我们确实了解它们运行的原理。但对于许多更深层次的认知任务，我们不知道。没错。那么，让我问一下，你也一直在从事生物信息学方面的工作。你是否惊叹于基本构建块，如果我们退一步看看我们人类，进化用来构建我们这些有智能的人类的构建块，都包含在我们的 DNA 中。这很神奇，而且真正神奇的是，我们开始学会编辑 DNA，这非常非常迷人。这种能够找到基因组中的序列并对其进行操作的能力，我的意思是，这真的将我们的生物系统推向了算法的世界。是的，但这引发了很多问题。你必须区分在个体上进行编辑，还是在某人的生殖系上进行编辑，这意味着所有后代都将受到影响。所以，这就像一个道德问题。所以，它引发了非常严重的道德问题。而且，即使在个体上进行编辑，也是如此，所以其中涉及很多傲慢，因为你认为敲除某个特定基因会有益，因为你不知道它会有什么副作用。所以，我们拥有这个精彩的基因编辑新世界，它非常非常令人印象深刻，而且它可以用于农业，可以用于医学的各种方式，但是，非常严重的道德问题出现了。对你来说，算法在伦理方面特别具有挑战性的地方是什么？我认为我们将不得不解决所有基因工程问题，但在算法方面，有很多好处是可能的。所以，有没有一些领域，你看到了算法在建模、优化、研究生物系统方面的激动人心的可能性？是的，我的意思是，我们当然可以分析基因组数据，以找出哪些基因在细胞中起作用，在什么条件下起作用，哪些蛋白质相互影响，哪些蛋白质在物理上相互作用。我们可以对蛋白质进行测序和修饰。这其中有什么是计算机科学问题，还是仍然是根本上的生物学问题？这绝对是一个大数据、统计大数据问题。所以，你知道，生物数据集正在增加我们研究祖先的能力，研究疾病的倾向，根据我们的基因组和我们对疾病的倾向来个性化治疗，以预测未来可能出现的麻烦并预见它们，以了解女性是否，她患乳腺癌的倾向是否足够强，以至于她想采取行动来避免它。你将你 1985 年的图灵奖演讲献给了你父亲的纪念。你对你父亲最美好的回忆是什么？看到他站在黑板前，用手画出完美的圆圈，并展示了他吸引一群三教九流的八年级学生兴趣的能力。你什么时候有机会看到他画完美的圆圈？偶尔，我会偷偷溜进他的教室观察。我认为他在教室里表现最好，我认为他真的活了过来，玩得很开心，不仅是教学，而且是与学生闲聊，并赢得学生的喜爱。我从他那里继承了强烈的教学愿望。我最近退休了，我的许多前学生都来了，和我一起做过研究的学生，或者读过我的论文的学生，或者上过我的课的学生。当他们谈论我时，他们谈论的不是我的 1979 年论文或我的 1992 年论文，而是他们从我的课上学到的东西，不仅仅是细节，而是教学方法和方式。所以，我至少在我担任布兰代斯大学教职的早期，我为我的讲座做了模范准备，我总是做足了准备，因此能够根据课堂上发生的事情进行偏离，并真正为学生提供榜样。所以，你有什么建议可以给其他人如何成为一名好老师吗？所以，准备是一回事，你已经提到了异常充分的准备，但还有其他建议可以传授吗？最重要的三点是准备、准备和准备。为什么准备如此重要？我猜是因为它让你能够轻松地应对课堂上出现的任何情况。而且，你知道，如果你发现你无法通过一种方式传达，你可以用另一种方式。如果学生有问题，你可以处理问题。最终，你也在感受人群，学生们在挣扎什么，他们理解了什么，只是通过问题。但即使只是通过他们的眼睛。而且，由于准备充分，你可以跳舞，你可以跳舞，你可以换一种说法，或者从另一个角度来说。在计算机科学中，有没有一些特别的想法和算法，你觉得对学生来说是巨大的“啊哈”时刻？他们是，因为某些原因，一旦他们明白了，就豁然开朗了，他们就爱上了计算机科学，还是因人而异？因人而异。你必须以不同的方式与学生打交道。有些人只需要很少的影响，你知道，他们只是在做他们的事情，他们只需要倾听。而另一些人则需要一点推动，另一些人需要被说服与他人合作，而不是独自工作。他们有自己的起起落落，所以你必须把每个学生当作一个人来对待，并发挥出最好的。人类很复杂。也许是个愚蠢的问题，如果你能重温生命中一个让你真正快乐的时刻，或者因为它以一种深刻的方式改变了你人生的方向，你会选择哪个时刻？我本科时是个懒学生，甚至研究生一年级也是。我认为是我开始做研究的时候。我有几个暑期工作，我能够做出贡献，我有一个想法。然后有一门关于运筹学数学方法的课程，我简直是囫囵吞枣地吸收了材料，我的分数比班上任何人都高 20 分。这引起了教职员工的注意，让我意识到我有一些能力，一些能力会走向某个方向。你意识到你在这方面做得很好。我认为没有更好的方式来结束它。理查德，这是一项巨大的荣誉。感谢您几十年来令人难以置信的工作。感谢您接受采访。非常荣幸，而且您是一位出色的采访者。我将停止。感谢收听理查德·卡普的这次谈话，也感谢我们的赞助商 Eight Sleep 和 Cash App。请考虑通过访问 eightsleep.com/lex 来支持这个播客，查看他们的超棒的床垫，并下载 Cash App 并使用代码 lex podcast。点击链接，购买商品，即使只是访问网站，但考虑购买也能帮助他们知道这个播客值得支持。这真的是支持我这段旅程的最好方式。如果你喜欢这个节目，请在 YouTube 上订阅，给它五星好评，在 Nappa Podcast 上支持它，或者在 Twitter 上与我联系，用户名是 lex friedman，如果你能拼对的话。现在，让我用艾萨克·阿西莫夫的一句话来结束：我不害怕电脑，我害怕缺乏电脑。感谢您的收听，希望下次再见。

Get Our Mobile App

Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111

Transcription