介绍
想象一下，您正在寻求理解计算的本质。你身处荒野深处，远离任何道路， 高深莫测 条未读消息 被雕刻在你周围的树干上——BPP，AC0[米]，Σ2P、YACC 和其他数百个。这些符号试图告诉你一些事情，但是从哪里开始呢？你甚至无法让它们全部保持直线。
很少有研究人员能做到这一点 罗素因帕利亚佐 打破这看似混乱的局面。 40 年来，Impagliazzo 一直致力于计算复杂性理论的前沿，研究不同问题的内在难度。该领域最著名的开放性问题称为 P 与 NP 问题，它询问许多看似困难的计算问题是否实际上很容易——只要使用正确的算法。答案将对科学和现代密码学的安全产生深远的影响。
在 1980 世纪 1990 年代和 XNUMX 年代，Impagliazzo 在统一 密码学的理论基础。 1995 年，他在一篇标志性论文中阐明了这些新发展的重要性，该论文用以下语言重新阐述了 P 与 NP 的可能解决方案以及一些相关问题： 五个假设的世界 我们可能会居住在被异想天开地称为 Algorithmica、Heuristica、Pessiland、Minicrypt 和 Cryptomania 的地方。因帕利亚佐的五个世界启发了一代研究人员，他们继续指导蓬勃发展的子领域的研究 元复杂性.
这些并不是他唯一梦想的世界。 Impagliazo 一生都是《龙与地下城》等桌面角色扮演游戏的爱好者，他乐于发明 新规则 以及可供探索的新设置。同样的顽皮精神也为他 30 年的即兴喜剧创作注入了活力。
Impagliazzo 还做了基础工作，阐明了随机性在计算中的基本作用。在 1970 世纪 XNUMX 年代末，计算机科学家发现随机性有时可以 改进算法 解决本质上的确定性问题——这一违反直觉的发现多年来一直困扰着研究人员。因帕利亚佐与复杂性理论家的合作 阿维威德森 和 1990 世纪 XNUMX 年代的其他研究人员表明，如果某些计算问题确实从根本上来说是困难的，那么它 总是有可能 将使用随机性的算法转换为确定性算法。相反，证明可以从任何算法中消除随机性 也将证明 确实存在困难的问题。
广达 与 Impagliazzo 讨论了难题和难题之间的区别、咨询神谕以及即兴喜剧的数学课程。为了清晰起见，采访内容已经过精简和编辑。
介绍
您什么时候第一次对数学产生兴趣？
在我真正知道数学是什么之前，我就对数学感兴趣了。三年级时，我的数学成绩开始下滑，因为我们要记住乘法表，但我拒绝了。我妈妈说：“但是拉塞尔，你喜欢数学，你为什么不这样做呢？”我说：“那不是数学，那是记忆。真正的数学不涉及记忆。”那时我学到的只是算术，所以我不确定我从哪里得到数学是关于抽象概念的概念。
计算机科学呢？该领域的某些部分非常抽象，但它们并不是大多数人第一次遇到的。
高中时，我学过 BASIC 编程课程，但完成任何事情都非常困难。这些程序必须转移到纸带上，纸带必须通过这台非常旧的计算机运行，该计算机经常发生故障并将你的纸撕成两半。所以我认为计算机科学非常枯燥。
我本来打算学习逻辑。但是，当您尝试实际形式化许多概念时，它们涉及计算，尤其是计算的限制。诸如“我们如何知道数学中的事物是真实的？”之类的问题以及“我们如何理解做数学的困难？”导致了理论计算机科学，尤其是复杂性理论。
您最著名的一些作品探讨了密码学和计算复杂性理论之间的联系。为什么这两个领域相关？
当您设置加密系统时，您需要区分合法用户（您想要授予访问权限的人）和其他人。计算困难的问题为我们提供了一种根据这些群体所知道的知识来区分这些群体的方法。但如果你想知道一个问题的答案来区分两组人，你就不能只使用任何困难的问题——你需要一个困难的谜题。
介绍
问题和谜题有什么区别？
一般来说，提出问题的人可能不知道答案。谜题是在设计时考虑到答案的问题。那么我们为什么需要拼图呢？因为我们需要能够确定一个被认为解决了这个问题的人是否真的解决了这个问题。在日常生活中，我们使用拼图来娱乐，但我们也在课堂上使用它们来测试人们是否理解材料。这就是密码学中发生的情况：我们使用谜题来测试某人的知识。
这五个世界的区别在于他们如何回答“有困难的问题吗？”的问题。和“有困难的谜题吗？”
这些不同的答案如何发挥作用？
在第一个世界 Algorithmica 中，没有什么问题是困难的。你不必知道别人是如何设计你的问题的：你总是可以解决它。 Heuristica 说的是：“好吧，也许有些问题很难。”然后我们到达佩西兰，那里的许多问题都很困难，但大多数谜题并不困难。几乎任何我知道解决方案的问题，你也能解决。所有这些都不利于密码学。
在 Minicrypt 中，我可以创建我知道如何解决的谜题，但对您来说仍然具有挑战性。最后，在《Cryptomania》中，两个人可以站在窃听者可以听到的公共场所，一起创造一个对于窃听者来说仍然很难的谜题。
是什么促使你写五个世界的论文？
当时，人们知道 P 与 NP 问题的不同答案将对我们能够解决什么样的问题以及我们能够期望什么样的安全性产生很大的影响，但是不同形式的轻松性和 NP 形式之间的质的区别硬度不太清楚。
几年前有一篇非常有洞察力的论文，其中使用许多相互关联的问题和大约 20 个可能的答案来阐述这些区别。我想写五个世界论文的原因之一是我们在这几年里取得了巨大的进步。为 20 个可能的世界找到名称是很困难的。
介绍
那么为什么要这样定义它，将其视为具有古怪名称的不同世界呢？
我同意为一次会议写这篇论文。我熬夜试图弄清楚我要说什么，凌晨 1 点左右的某个时候，不同世界的框架似乎是个好主意。第二天早上我读到它，它看起来仍然是一个不错的想法——这是一种展示这些想法将如何真正影响世界的方式，而无需陷入定量细节。这篇论文最让我高兴的是，我从从事复杂性研究的人那里听说，这篇论文让他们作为本科生对该领域产生了兴趣。
研究人员是否排除了五个可能世界中的任何一个？
我们实际上正在添加更多内容——人们已经开始谈论 混淆乌托邦 作为一个拥有更强大的加密工具的世界。令人有点沮丧的是，我们在 1980 世纪 XNUMX 年代末取得了如此大的进步，但从那时起就没有消除任何世界。但另一方面，我们对世界之间的联系了解更多，并且对 更清晰的图片 每个世界都会是什么样子。
假设世界在复杂性理论中还发挥着另一个作用，即在假设“神谕”存在的证明中发挥着作用。那么，首先，什么是预言机？
想象一下，有人建造了一个巧妙的设备，可以解决某些问题，而我们不知道解决该问题的算法。这就是神谕。如果我们有这样一个神奇的设备，并将其放入计算机中，它可能会改变可计算和不可计算之间的界限。
介绍
研究人员认为这些魔盒真的存在吗？
不，它们可能不存在。早期，甲骨文的结果有些争议，因为它们过于假设。但它们非常有启发性的一种方式是，当使用预言机来模拟理想情况时。假设你试图证明 A 并不一定意味着 B。你从具有最极端 A 的设置开始，并表明这仍然不足以保证 B。如果你可以证明即使所有的可能性都是对你有利，你仍然无法证明某件事，这是非常有力的证据，表明它很难证明。
您还发现了计算难度和随机性之间的联系。这种连接如何运作？
这实际上是一种说法，如果你不理解某件事，那么它可能看起来是随机的。假设我说我正在考虑一到一千之间的数字。如果我随机选择一个数字，你猜到的机会是千分之一。如果我问——按照巨蟒剧团的说法——“欧洲燕子的平均空速是多少？”你也有同样的机会。它可能每小时行驶超过一英里，也可能不会超过每小时一千英里。
这实际上并不是随机的——这是一个可以确定地回答的问题。我们可以测量所有飞来飞去的燕子，但在资源有限的情况下很难确定，比如没有测量燕子速度的预算，也没有无限供应的燕子。
因此，我们的见解是，我们不知道其解决方案的难题可以提供看起来随机的“伪随机”数字的来源。
介绍
说到巨蟒剧团，我知道你已经从事即兴喜剧很长时间了——你是怎么开始的？
1991 年，我开始在圣地亚哥担任助理教授。大约在 94 年左右，我想，“我在系外真的没有太多生活。”所以我得到了免费的周报，并浏览了俱乐部和活动的列表。我排除了除了即兴喜剧之外的一切——我认为至少我可以胜任。我在初级班认识了我的妻子。
她是怎么想的？
她说我真的很糟糕。当你是一名逻辑学家时，你接受的训练就是始终思考每个单词的细微差别。你不想说一些不正确的话。即兴表演的伟大之处在于它扭转了这一点：重点不是说一些完美的话，而是快速弥补一些东西。这与我的余生相反。
我现在的妻子休了一次课，一年后她回来时，我给她留下了深刻的印象。那是30年前的事了。我仍然在同一位老师的指导下上同一堂课。
即兴创作是否改变了您的研究方式？
不要对你的每一个想法都吹毛求疵，这是一个很好的做法。这对于合作特别有帮助。当与其他人一起工作时，我常常这样说：“但是这个想法行不通，原因如下。这实际上不是真的。”在即兴表演中，你总是应该接受你的搭档所说的话。我认为这是一个很好的态度，尤其是当你和学生一起做研究时：不要仅仅因为你知道他们所说的不正确而忽视他们所说的东西。有很多好的想法并不是 100% 正确。
介绍
像什么？
当你试图获得对问题的直觉时，有帮助的一件事就是从一些简化的假设开始。这些假设通常并不正确，但它们可以帮助您制定路线图。说：“如果我有一头大象，我就可以翻山越岭。当然，我没有大象。但如果我这样做的话，我会这样做。”然后你意识到，“好吧，也许我不需要大象来完成这一步。骡子就好了。”
你对角色扮演游戏的热爱怎么样——这对你的工作有影响吗？
它可能不会影响我所有的研究，但它确实影响了我的五个世界论文。我一直对奇幻和科幻小说很感兴趣，并想出不同的可能世界——如果一切都不同的话，事情会是什么样子？
为什么角色扮演游戏是探索假设世界的一种引人注目的方式？
热衷于推理小说的人总是会创造一些世界。托尔金因此而闻名，他拥有如此丰富的想象力，以至于他的世界实际上让人感觉生活在其中。对于我们这些缺乏想象力的人来说，实现这一目标的最佳方法就是邀请人们进入你的环境，然后玩游戏是这样做的一种方法。现在这不仅仅是我的世界。它可能是按照我想象的方式开始的，但就像任何合作一样，由于其他人的贡献，它已经远远超出了这个范围。
