Russell Impagliazzo：通过创造新世界探索计算的本质
原文： https://www.quantamagazine.org/the-researcher-who-explores-computation-by-conjuring-new-worlds-20240327/
作者：Ben Brubaker
译者：Kurt Pan
想象一下，你正在探索计算的本质。你深入荒野，远离任何道路，周围的树干上刻着无法解读的信息——，，，，还有其他数百种。这些符号试图告诉你一些事情，但你应该从哪里开始呢？你甚至都无法把它们全部记住。
很少有研究者像 Russell Impagliazzo 那样深入地研究这片混沌。在过去的 40 年里，Impagliazzo 一直在计算复杂性理论的前沿工作，该理论研究不同问题的固有难度。这个领域最著名的开放问题，被称为 P 与 NP 问题，即许多看似困难的计算问题是否实际上是简单的——只要有正确的算法。对此的一个回答将对科学和现代密码学的安全产生深远影响。
在 1980 年代和 1990 年代，Impagliazzo 在统一密码学的理论基础方面发挥了主导作用。1995 年，他在一篇著名的论文中阐述了这些新进展的重要性，该论文以五个我们可能居住的假定世界的语言重新阐述了 P 与 NP 的可能解决方案以及一些相关问题，这五个世界被他幽默地命名为 Algorithmica、Heuristica、Pessiland、Minicrypt 和 Cryptomania。Impagliazzo 的五个世界激发起了一代研究者的灵感，他们继续导致了元复杂性子领域的研究的繁荣。
这些还不是他唯一构想出的世界。Impagliazzo 一生都是桌面角色扮演游戏如《龙与地下城》的狂热爱好者，他喜欢发明新的规则和新的环境以进行探索。同样的玩心也激发了他 30 年的即兴喜剧实践。
Impagliazzo 还对阐明计算中随机性的根本角色做出了基础性的工作。在 1970 年代末，计算机科学家发现随机性有时可以改进解决固有确定性问题的算法——这是一个令研究人员困惑多年的反直觉发现。Impagliazzo 在 20 世纪 90 年代与复杂性理论家 Avi Wigderson 和其他研究人员的工作表明，如果某些计算问题真的是根本上困难的，那么总是可以将使用随机性的算法转换为确定性的算法。反之，证明任何算法都可以消除随机性，也就将证明真正的困难问题的存在。
下面是Quanta 与 Impagliazzo 就困难问题与难解的谜题之间的区别、查询神谕，以及即兴喜剧的数学课程进行了交谈。为了清晰明了，这次采访已经被压缩和编辑过。
你是什么时候开始对数学感兴趣的？
在我真正了解数学是什么之前，我就对它感兴趣了。在三年级时，我的数学成绩开始下滑，因为我们被要求记住乘法表，而我拒绝了。我的母亲说：“但是 Russell，你喜欢数学啊，为什么你不做这个？”我回答说：“那不是数学，那是记忆。真正的数学并不涉及记忆。”那时我所学的只是算术，所以我并不确定我是从哪里得到数学是关于抽象概念的观念的。
那计算机科学呢？这个领域的部分内容是非常抽象，但这些并不是大多数人首次接触时遇到的。
在高中时，我上过一门 BASIC 语言编程课程，但是要真正完成一些事情真的很难。程序必须转存到纸带上，然后通过一台经常出故障并且会把你的纸撕成两半的非常旧的计算机去运行。所以我认为计算机科学极其乏味。
我原本打算研究逻辑。但是，当你试图去真正形式化许多概念时，它们会涉及到计算，尤其是计算的极限。像“我们如何知道数学中的对象是真的？”和“我们如何理解做数学的难度？”这样的问题引导我走向了理论计算机科学，尤其是复杂性理论。
你最知名的一些工作探索了密码学和计算复杂性理论之间的联系。这两个领域为什么会有关联呢？
当你正在设计一个密码系统时，你需要区分开合法用户——你想授予访问权限的人——和其他所有人。计算困难的问题为我们提供了一种基于他们所知的知识来区分这些群体的方法。但是，如果你想让知道问题答案成为区分两组人的方式，你还不能仅仅使用任意困难问题——你需要的是一个难解的谜题。
问题和谜题之间有什么区别？
总的来说，提出问题的人可能并不知道答案。谜题是一种有答案在心里时设计的问题。那么我们为什么需要谜题呢？因为我们需要能够确定一个声称解决了它的人是否真的解决了。在日常生活中，我们用谜题来娱乐，但我们也在课堂上使用它们来测试学生是否理解了材料。这就是密码学中发生的事情：我们使用谜题来测试某人的知识。
五个世界之间的区别就在于它们如何回答“是否存在困难问题？”和“是否存在难解的谜题？”这两个问题。
那些不同的答案是如何展现的？
在第一个世界，Algorithmica，没有问题是困难的。你不需要知道别人是如何设计你的问题的：你总能解决它。Heuristica是说，“嗯，可能有几个问题很难。”然后我们来到Pessiland，那里有很多困难问题，但大多数谜题并不难。几乎所有我能想出来并知道答案的问题，你也能解决。所有这些世界对密码学来说都不好。
在 Minicrypt 中，我可以创建一些我知道如何去解决的谜题，但对你来说仍然非常具有挑战性。最后，是Cryptomania，在这个世界中，两个人可以站在一个窃听者可以听到的公共地点，一起去创建一个对窃听者来说仍然很难的谜题。
是什么激励你写下那篇五个世界的论文？
当时，众所周知的是对 P 与 NP 问题的不同回答将对我们能解决的问题类型以及我们可以期待的安全性类别产生重大影响，但是不同形式的难易度之间的定性区别并不真正清晰。
就在那几年前，有一篇非常有洞察力的论文，通过许多相互关联的问题，列出了大约 20 个可能答案的区别。我之所以想写这篇关于五个世界的论文，是因为我们在那几年里取得了巨大的进步。毕竟要为 20 个可能的世界找到名称都将会很困难。
那么，为什么要以这种带有古怪名称的不同世界的框架来表述呢？
我曾答应给一个会议撰写这篇论文。我熬夜深思，试图弄清楚我要说什么，大约在凌晨 1 点时，我觉得不同的世界的表述似乎是个好主意。然后我在第二天早上读了它，它仍然像一个可接受的主意——这是一种展示这些想法实际上如何会影响世界而不必陷入量化细节的方式。这篇论文让我最开心的是，我听到复杂性研究人员说，这是他们在本科阶段对这个领域产生兴趣的那篇论文。
研究人员有排除五个可能的世界中的任何一个吗？
实际上，我们正在增加更多——人们已经开始讨论 Obfustopia了，作为一个拥有更强密码学工具的世界。我们在 1980 年代末取得了如此多的进步，但自那时以来并未排除掉任何世界，这多少有点令人沮丧。但另一方面，我们对各个世界之间的联系了解得更多了，对每个世界的样貌有了更清晰的认识。
假定的世界在复杂性理论中也扮演着另一种角色，即在假设“神谕”存在的证明中。那么首先，什么是神谕呢？
想象一下，有人构建了一个神奇的设备，可以解决我们不知道解决算法的问题。这就是神谕的作用。如果我们有这样一个神奇的设备，并将其放入我们的计算机中，它就会改变可计算和不可计算之间的界限。
研究者认为这些魔术盒子真的可能存在吗？
不，他们可能并不存在。早期，神谕结果有些争议性，因为它们太假设性了。但是，当神谕被用来模拟理想情况时，它们可以非常有启发性。假设你正在试图证明 A 并不一定蕴含 B。你从最极端的 A 的设定开始，证明这仍然不足以保证 B。如果你能证明即使所有可能都对你有利，你仍然不能证明某件事，那就是非常有力的证据，证明这将是难以证明的。
你还发现了计算困难性和随机性之间的联系。这种联系是怎样的？
这实际上是在说，如果你不理解某件事，那么它看起来可能就是随机的。假设我说我在想一个一到一千之间的数字。如果我随机选择数字，你有千分之一的机会猜中它。而如果我问——按照Monty Python的说法——“欧洲燕子的平均飞行速度是多少英里/小时？”你的猜测成功概率大约也是一样的。它可能比每小时一英里要快，但可能不会超过每小时一千英里。
这并非真正的随机性 - 这是一个可以确定性回答的问题。我们可以测量所有飞来飞去的燕子，但是在资源受限的情况下，这种确定性就变得有些困难，比如没有预算来测量燕子的飞行速度，也没有无限的燕子供应。
所以，这里的洞察是，我们不知道解决方案的困难问题可以提供看起来随机的“伪随机”数源。
说到 Monty Python，我知道你已经做即兴喜剧很长时间了——你是怎么开始的？
我于 1991 年在圣地亚哥开始担任助理教授。大约在 94 年左右，我想，“我在系里以外的生活真的不多。”所以我拿了免费的每周报纸，浏览了一下俱乐部和活动的列表。我排除了所有的东西，只留下了即兴喜剧——我认为我至少有可能去做得不错。我在那个初级班上遇到了我的妻子。
她觉得怎么样？
她说我真的很糟糕。当你是一个逻辑学家，你被训练为去总是思考每个词的细微差别。你不想说出错误的东西。但即兴表演在这方面很棒，因为它颠覆了这一点：重点不是说出完美的东西，而是快速编造出东西。这与我生活的其他部分完全相反。
我现在的妻子曾经暂时离开了那个课程，一年后当她回来时，我成功地打动了她。那是 30 年前的事了。我仍然在跟同一个教练上同样的课。
做即兴表演改变了你进行研究的方式吗？
对于你所想的每一件事不吹毛求疵，这是一个好习惯。这在合作中尤其有帮助。在与他人共事时，我过去常常会说：“但是那个想法不会奏效，原因如下。这不是正确的。”在即兴表演中，你总是应该接受你的搭档所说的话。我认为这是一个好的态度，尤其是当你与学生进行研究时：不要仅仅因为你知道它是错误的就否定他们说的话。有很多好的想法并不是 100%正确的。
比如呢？
当你试图理解一个问题时，有一种有用的方法是从一些简化的假设开始。这些假设通常并不真实，但它们可以帮助你制定一个路线图。比如说，“如果我有一头大象，我就能越过山脉。当然，我并没有大象。但如果我有，我会这样做。”然后你会意识到，“嗯，也许我在这一步并不需要大象。一头骡子就足够了。”
你对角色扮演游戏的热爱是否对你的工作产生了影响？
它可能并未影响我所有的研究，但它确实影响了我的五个世界的论文。我一直对奇幻和科幻有着普遍的兴趣，喜欢构想不同的可能世界——如果一切都不同，事情会变成什么样子？
为什么角色扮演游戏是探索假定世界的一种引人入胜的方式？
喜欢幻想小说的人总是善于创造世界。托尔金在这方面最为出名的，他的想象力如此强大，以至于他所创造的世界真的给人一种栩栩如生的感觉。对于我们这些想象力不够强大的人来说，最好的实现方式就是邀请人们进入你的设定，而游戏就是一种实现方式。现在这已经不仅仅是我的世界了。它可能是从我的想象开始，但就像任何合作一样，由于每个人的贡献，它已经从那里演化到了很远。
Kurt Pan 翻译后记：太喜欢这个采访了！除去引用量、会议分区等世俗指标，评判一篇论文是否重要还有一个重要的判据：这篇论文能否引起一个本科生对一个领域的兴趣。某种程度上讲，这才是最重要的指标。毫无疑问，"五个世界"就是这样伟大的论文。因为它Make Cryptography Interesting Again! 还有hardness vs randomness: 如果你不理解某件事，那么它看起来可能就是随机的。这是多么深刻的洞见啊！我虽然没有像Yanyi Liu这样优秀的研究者一样一头扎进这个产出极度不确定的兔子洞的勇气（也几乎没有这样的环境），但依然对此保有初心，有着最简单直接的兴趣。