ACM通信

贡献的文章

五十年的P与NP以及不可能的可能性

由兰斯Fortnow
ACM通信，2022年1月，第65卷第1号，76-85页
10.1145 / 3460351
评论

1971年5月4日，计算机科学家/数学家史蒂夫·库克在他的论文《定理证明过程的复杂性》中向世界介绍了P vs. NP问题。50多年后，世界仍在努力解决这个问题。事实上，我在12年前的一篇通信文章“P与NP问题的现状”。¹³

回到顶部

关键的见解

自2009年的那篇文章以来，P vs NP问题及其背后的理论并没有发生巨大的变化，但计算世界肯定发生了变化。云计算的发展为社交网络、智能手机、零工经济、金融科技、空间计算、在线教育赋能，或许最重要的是，数据科学和机器学习的兴起。2009年，市值排名前十的公司中只有一家大型科技公司:微软。截至2020年9月，前七名分别是苹果、微软、亚马逊、Alphabet(谷歌)、阿里巴巴、Facebook和腾讯。³⁸美国计算机科学(CS)毕业生的数量增加了两倍多⁸而且远远不能满足需求。

我没有简单地修改或更新2009年的调查，而是选择通过P与NP的视角来观察计算、优化和机器学习方面的进展。我关注的是这些进步如何让我们更接近一个P = NP的世界，P vs. NP仍然存在的局限性，以及由此产生的新的研究机会。特别地，我将研究我们如何走向一个我称之为“Optiland”的世界，在那里，我们几乎可以奇迹般地获得P = NP的许多优点，同时避免一些缺点，比如破解密码学。

作为一个开放的数学问题，P vs. NP仍然是最重要的问题之一;它被列在克莱数学研究所的千年难题上²¹(该组织为解决这个问题提供了100万美元的赏金)。我通过描述一些新的计算机科学理论结果来结束这篇文章，这些结果虽然没有让我们更接近解决P vs. NP问题，但向我们表明，对P vs. NP的思考仍然推动了该领域的许多重要研究。

回到顶部

P和NP问题

Facebook上有300个用户彼此都是好友吗?你会如何回答这个问题?假设你在Facebook工作。你可以访问整个Facebook图表，并可以看到哪些用户是好友。现在需要编写一个算法来找到这个大的朋友圈。您可以尝试所有的300组，但是太多了，无法全部搜索。你可以尝试一些更聪明的方法，也许从小团队开始，然后将他们合并到更大的团队中，但你所做的一切似乎都不起作用。事实上，没有人知道有比尝试所有组更快的解决方案，但我们也不知道不存在这样的解决方案。

这基本上就是P和NP的问题。NP代表有解决方案的问题，你可以有效地检查。如果我告诉你哪300个人可能会形成一个小圈子，你可以相对较快地确认这44850对用户都是朋友。集团是一个NP问题。P表示你能有效找到解决方案的问题。我们不知道小集团问题是否在P中，也许，令人惊讶的是，小集团有一个叫做NP完全的性质，即当且仅当P = NP时，我们可以快速有效地解决小集团问题。许多其他的问题也有这个性质，包括3-着色(地图可以只用三种颜色来着色，这样相邻的两个国家就不会有相同的颜色了吗?)旅行推销员(在一系列城市中找到最短的路线，访问每一个城市，然后返回起点)，还有成千上万的其他城市。

形式上，P代表“多项式时间”，这类问题可以在输入长度上以一个固定的多项式为界的时间内解决。NP代表“非确定性多项式时间”，在这里，人们可以使用一个非确定性机器，它可以神奇地选择最佳答案。出于本调查的目的，最好将P和NP简单地认为是高效可计算和高效可检验的。

对于那些想要对P vs. NP问题的重要性进行更长的非正式讨论的人，请参阅2009年的调查¹³或者是基于调查的科普书籍。¹⁴关于更专业的介绍，请参阅迈克尔·加里(Michael Garey)和大卫·约翰逊(David Johnson) 1979年出版的书¹⁶对于那些需要理解哪些问题是np完整的人来说，它仍然是一个非常宝贵的参考。

回到顶部

为什么现在谈论它?

1971年的那个周二下午，库克在位于俄亥俄州Shaker Heights的Stouffer’s Somerset Inn向ACM计算机理论研讨会的与会者发表了他的论文，他证明了这一点可满足性非完全多项式,无谓的重复是np困难的。¹⁰这些定理表明，对于不在[P]中的有趣集合，重言同义是一个很好的候选者，我觉得花相当大的精力来证明这个猜想是值得的。这样的证明将代表复杂性理论的重大突破。

确定一个数学概念的时间几乎总是一个挑战，还有许多其他可能的时间我们可以开始P与NP时钟。算法和证明的基本概念至少可以追溯到古希腊，但据我们所知，他们从未考虑过像P对NP这样的普遍问题。高效计算和非决定论的基础知识是在20世纪60年代发展起来的。P和NP问题早在那之前就有了，只是我们不知道而已。

---

P vs NP问题及其背后的理论并没有发生巨大的变化，但计算世界肯定发生了变化。

---

库尔特Gödel写了一封信¹⁷1956年给约翰·冯·诺伊曼的论文，基本上描述了P与NP问题。尚不清楚当时身患癌症的冯·诺伊曼是否读过这封信，这封信直到1988年才被发现并广泛传播。直到理查德·卡普1972年发表了他的论文，P vs. NP问题才真正成为一种现象²³表明大量著名的组合问题是np完全的，包括Clique, 3-Coloring，和Traveling Salesman。1973年，列昂尼德·莱文(Leonid Levin)在他1971年的独立研究基础上发表了一篇论文，定义了P与NP问题。²⁷当莱文的论文传播到西方的时候，P vs NP已经成为了计算领域最重要的问题。

回到顶部

Optiland

Russell Impagliazzo，在1995年的一篇经典论文中，^20.描述了P与NP问题的五个不同可能性的世界:

• Algorithmica:P = NP或“道德等效”的东西，比如NP的快速概率算法。
• Heuristica:NP问题在最坏的情况下很难，但在平均情况下很容易。
• Pessiland:我们可以很容易地创造出难的NP问题，但不是我们知道解的难NP问题。这是所有可能的世界中最糟糕的，因为我们既不能解决困难的问题，也不能从这些问题的困难中获得任何明显的密码优势。
• Minicrypt:加密单向函数是存在的，但我们没有公钥加密。
• Cryptomania:公钥加密是可能的——也就是说，双方可以在开放通道上交换秘密消息。

这些世界是故意没有正式定义的，而是暗示了我们对P与NP问题的知识的未知可能性。人们普遍认为，我们生活在Cryptomania(密码癖)中。

Impagliazzo借鉴了P与NP理论中的“你不可能拥有一切”。你既可以解决困难的NP问题，也可以使用密码学，但你不能两者兼得(两者都不能)。也许，我们正在走向一个事实Optiland。机器学习和软硬件优化方面的进步，使我们能够在长期被认为困难或不可能的问题上取得进展——从语音识别到蛋白质折叠——然而，在大多数情况下，我们的密码协议仍然是安全的。

在2009年调查中名为“如果P=NP会怎样?”的章节中，¹³我写道:“通过使用奥卡姆剃刀原理，学习变得很容易——我们只需找到与数据一致的最小程序。近乎完美的视觉识别、语言理解和翻译，以及所有其他学习任务都变得微不足道。我们还将对天气、地震和其他自然现象有更好的预测。”

如今，你可以使用面部扫描解锁智能手机，与智能手机交谈，向它提问，通常会得到一个合理的答案，或者将你的问题翻译成其他语言。你的手机会收到天气和其他气候事件的警报，它的预测能力比我们十几年前想象的要好得多。与此同时，密码学几乎毫发无损，除了对小密钥长度的野蛮攻击。现在让我们看看计算、优化和学习方面的最新进展是如何将我们引向Optiland的。

回到顶部

解决困难的问题

2016年，比尔·库克(与史蒂夫没有关系)和他的同事们决定应对以下挑战:⁹你如何尽可能在最短的距离内参观英国的每个酒吧?他们列出了24727家酒吧的名单，并创造了终极的酒吧爬行，这是一次跨越45495239米(约28269英里)的步行之旅，比绕地球一圈还长。

库克做了一些手脚，为了保持规模合理，他取消了一些酒吧。在英国的一些媒体报道之后，⁷许多人抱怨错过了他们最喜欢的酒吧。库克和他的同事们重新开始工作，名单上的酒吧数量增加到了49687家。新的旅行长度将是63,739,687米，或约39,606英里(见数字)．人们只需多走40%的路就能到达两倍多的酒吧。爬酒吧只是一个旅行推销员问题，np完全问题中最著名的一个。49687家酒吧中可能的游览次数大概是3个后面跟着211761个零。当然，库克的计算机不会搜索整个行程，而是使用各种优化技术。更令人印象深刻的是，这次旅行还提供了一个基于线性程序对偶的最优性证明。

数字最短路线途经49687家英国酒吧。所使用的许可。（http://www.math.uwaterloo.ca/tsp/uk)．

为了完成一项更大的任务，库克和他的同事们打算通过计算200多万颗恒星之间的距离，找到最短的旅行路线。他们的行程为28884456秒差距，距离最佳行程仅683秒差距。

除了《旅行推销员》，我们还看到了在求解可满足性和混合整数规划方面的重大进展——混合整数规划是线性规划的一种变体，其中一些(但不是所有)变量必须是整数。使用高度精炼的启发式算法、快速处理器、专用硬件和分布式云计算，通常可以解决在实践中使用数万个变量和数十万甚至数百万个约束时出现的问题。

面对一个要解决的NP问题，人们通常可以把这个问题表述为一个可满足性或混合整数规划问题，并把它扔给一个顶级求解者。这些工具已经成功地用于电路和代码的验证和自动化测试、计算生物学、系统安全、产品和包装设计、金融交易，甚至解决一些困难的数学问题。

回到顶部

数据科学与机器学习

任何的读者通信大多数人都不能忽视机器学习的变革效应，尤其是通过神经网络学习。用人工神经元(基本上是计算加权阈值函数的对象)来建模计算的概念可以追溯到20世纪40年代Warren McCulloch和Walter Pitts的工作。²⁸20世纪90年代，Yoshua Bengio Geoffrey Hinton和Yann LeCun²⁶开发了基本的算法来驱动神经网络的学习，这些神经元的电路有好几层。更快、更分布式的计算、专门的硬件和海量的数据帮助推动了机器学习，使其能够出色地完成许多面向人类的任务。ACM认识到Bengio、Hinton和LeCun的工作对我们的社会产生了不可思议的影响图灵奖。

机器学习如何与P和NP相结合?在这一节中，当我们讨论P = NP时，它将是一个非常强烈的意义，即NP中的所有问题在实践中都有有效的算法。奥卡姆剃刀说，“实体不应该在没有必要的情况下成倍增长”，或者通俗地说，最简单的解释可能是正确的。如果P = NP，我们可以利用这个思想创建一个强学习算法:找到与数据一致的最小电路。尽管我们可能没有P = NP，但机器学习可以近似这种方法，这导致了它令人惊讶的力量。然而，神经网络不可能是“最小”的可能电路。通过今天的深度学习技术训练的神经网络，其结构通常是固定的，参数只在导线上的权重上。为了有足够的表达能力，通常有数百万或更多这样的重量。这限制了神经网络的能力。他们在人脸识别方面做得很好，但他们不能根据例子学习乘法。

通用分发和GPT-3。考虑无限个二进制字符串集合上的分布。你不可能有一个均匀的分布，但你可以创建一个分布，每个相同长度的字符串有相同的概率。然而，有些字符串就是比其他字符串更重要。例如，π的前100万位数比随机产生的100万位数有更多的意义。你可能想把更高的概率放在更有意义的字符串上。有很多方法可以做到这一点，但实际上有一个通用分布，它接近于任何其他可计算分布(参见Kirchherr等人。²⁵这个分布与学习有很大的联系—例如，任何对这个分布进行小错误学习的算法将学习所有可计算的分布。问题是，即使P = NP，这个分布也是不可计算的。如果P = NP，我们仍然可以通过创建一个对其他有效计算分布通用的有效计算分布来得到一些有用的东西。

我们能从机器学习中得到什么?想想生成式预训练变压器(GPT)，尤其是2020年发布的GPT-3。⁵GPT-3有1750亿个参数，使用4100亿个令牌进行训练，这些令牌来自尽可能多的书面语料库。它可以回答问题，根据提示写文章，甚至编写代码。虽然GPT-3还有很长的路要走，但它已经因为能够生成看起来像人类生产的材料而获得了热烈的评价。我们可以把GPT-3看作是一种分布，我们可以看到由算法产生的输出的概率，这是通用分布的弱版本。如果我们限制一个通用分布有一个给定的前缀，那么就会提供一个由该前缀提示的随机样本。GPT-3也可以建立在这样的提示基础上，无需进一步培训就能处理范围非常广泛的领域知识。随着这条研究路线的发展，我们将更接近一个可以执行内置学习的通用指标:从给定的上下文生成随机示例。

科学和医学。在科学方面，我们通过进行大规模模拟来理解，例如，探索核聚变反应，从而取得了进展。然后，研究人员可以应用一种形式的科学方法:为物理系统创建一个假设;用这个模型来做一个预测;然后，不要试图创造一个真实的反应，而是用一个实验模拟来测试这个预测。如果答案与预期的不一样，那么就改变或抛弃模型，重新开始。

在我们有了一个强大的模型之后，我们就可以在物理反应堆中进行昂贵的测试。如果P = NP，我们就可以，如上所述，使用奥卡姆剃刀方法来创建假设——找到与数据一致的最小电路。机器学习技术可以沿着这些路线工作，自动化假设的创建。给定的数据——无论是通过模拟、实验还是传感器生成的——机器学习可以创建与数据匹配的模型。我们可以使用这些模型进行预测，然后像之前一样测试这些预测。

虽然这些技术使我们能够找到可能被遗漏的假设和模型，但它们也可能导致假阳性。我们通常以95%的置信水平接受一个假设，这意味着20个糟糕的假设中有一个可能通过。机器学习和数据科学工具可以让我们产生假设，这些假设可能会冒着发表不符合事实的结果的风险。医学研究人员，尤其是那些试图解决癌症等疾病的研究人员，经常会遇到硬性的算法障碍。生物系统是极其复杂的结构。我们知道，我们的DNA形成了一种代码，描述了我们的身体是如何形成的，以及它们的功能，但我们对这些过程如何工作的了解非常有限。

2020年11月30日，谷歌旗下的DeepMind发布了基于氨基酸序列预测蛋白质形状的新算法AlphaFold。²²AlphaFold的预测几乎达到了通过实验建立氨基酸序列和测量形成蛋白质的形状的准确性。关于DeepMind是否真的“解决”了蛋白质折叠存在一些争议，现在评估其影响还为时过早，但从长远来看，这可能会给我们提供一个新的数字工具来研究蛋白质，了解它们如何相互作用，并学习如何设计它们来对抗疾病。

超越P和NP:象棋和围棋。NP就像解谜。数独，在一个任意大小的棋盘上，是NP-complete来解决给定的初始设置的数字在一些正方形。但如果是两名玩家轮流玩的游戏，如国际象棋和围棋，当我们问谁在给定的初始设置中获胜时，情况会如何?即使我们有P = NP，也不一定能得到一个完美的象棋程序。你可能会问，是否有白棋的一招，对于黑棋的每一步，都有白棋的一招，对于黑棋的每一步，白棋都赢。你不能只在P = NP的情况下做所有这些黑白交替。这类游戏通常被称为PSPACE-hard，对于使用合理数量的内存而没有任何时间限制的计算是困难的。国际象棋和围棋甚至可能更难，这取决于规则的精确制定(见Demaine和Hearn)。¹¹）

这并不意味着如果P = NP，你就不能得到一个好的象棋程序。如果可能的话，你可以找到一种有效的计算机程序，它的大小比所有小一点的高效程序都要好。与此同时，即使没有P = NP，计算机在国际象棋和围棋方面也变得非常强大。1997年，IBM的“深蓝”击败了当时的国际象棋世界冠军加里·卡斯帕罗夫(Gary Kasparov)，但即便是实力强大的业余棋手，围棋程序也难以取胜。机器学习已经极大地改善了电脑游戏。虽然有很长的历史，但让我跳到AlphaZero，它是谷歌的DeepMind在2017年开发的。³⁵

AlphaZero使用了一种被称为蒙特卡洛树搜索(MCTS)的技术，它随机地为两个玩家决定最佳行动方案。AlphaZero使用深度学习来预测游戏位置的最佳分布，从而优化使用MCTS的获胜机会。虽然AlphaZero不是第一个使用MCTS的程序，但它没有任何内置策略或访问以前的游戏数据库。AlphaZero只遵循游戏规则。这使得AlphaZero可以在国际象棋和围棋两种截然不同的游戏中都表现出色，除了交替走法和固定大小的棋盘之外，它们几乎没有什么共同点。DeepMind最近在MuZero上更进一步，³³它甚至没有完整的规则，只是一些棋盘位置的表示，一个合法的移动列表，以及位置是赢、输还是平。现在我们已经了解到，在国际象棋或围棋中，纯机器学习可以轻松击败任何人类或其他算法。人为干预只会碍手碍脚。对于像国际象棋和围棋这样的游戏，机器学习可以在P = NP还不够的情况下取得成功。

---

当机器学习面对的任务不是来自其训练的分布时，它可能不会做得很好。

---

可辩解的人工智能。许多机器学习算法似乎工作得很好，但我们不知道为什么。如果你观察一个经过语音识别训练的神经网络，你通常很难理解它为什么会做出这样的选择。我们为什么要关心?以下是一些原因。

• 信任:我们怎么知道神经网络是正确的?除了检查输入/输出对，我们不能做任何其他分析。不同的应用程序具有不同的信任级别。如果网飞公司推荐的电影不好，这没什么，但如果自动驾驶汽车推荐了一个错误的转弯，就不太好了。
• Fairness@:在许多例子中，训练数据的算法可以学习数据中有意和无意的偏差(参见O’neil)^30.)．如果你不理解这个程序，你如何找出偏差?
• 安全:如果你用机器学习来监控安全系统，你就不知道还有什么漏洞存在，尤其是当你的对手能够适应的时候。如果您能理解代码，就可以发现并修复安全漏洞。当然，如果对手有代码，他们可能会发现漏洞。
• 因果关系:现在，你最多只能检查机器学习算法是否只与你想要的输出相关联。理解这些代码可能有助于我们理解数据中的因果关系，从而推动更好的科学和医学。

如果P = NP，我们会得到更好的情况吗?如果你有一个处理np完全问题的快速算法，你可以用它找到最小的电路来匹配或旅行推销员，但你不知道为什么这个电路有效。另一方面，你想要一个可解释的算法的原因是这样你就可以理解它的性质，但我们可以用P = NP直接推导出这些性质。整个会议都在研究可解释的人工智能，比如ACM公平、问责和信任会议。

机器学习的局限性。虽然机器学习在过去十年中已经显示出了许多令人惊讶的结果，但这些系统还远远不够完美，在大多数应用中，仍然可以被人类打败。我们将继续通过新的和优化的算法、数据收集和专门的硬件来提高机器学习能力。机器学习似乎确实有其局限性。正如我们上面所看到的，机器学习将让我们体验到P = NP，但它永远无法取代它。机器学习在破解密码学方面进展甚微，我们将在文章后面看到这一点。

机器学习似乎无法学习简单的算术——例如，对大量数字求和或大数相乘。人们可以想象将机器学习与符号数学工具结合起来。虽然我们在定理证明方面取得了一些令人印象深刻的进展，¹⁹我们距离我的梦想任务还有很长一段路要走，我的梦想任务是用我的一篇研究论文，以及它的非正式证明，让一个人工智能系统填写细节并验证证明。

同样，P = NP会使这些任务变得容易或至少容易处理。当机器学习面对的任务不是来自其训练的分布时，它可能不会做得很好。这可能是低概率的边缘情况，例如来自一场比赛的人脸识别在训练数据中没有很好地表现出来，或者甚至是通过在输入中做一个小的改变来强制不同的输出的对抗性尝试——例如，改变停车标志的几个像素来强制算法将其解释为限速标志。¹²深度神经网络算法可以有数百万个参数，所以它们可能不能很好地推广分布。如果P = NP，人们可以产生最小尺寸的模型，有望在推广方面做得更好，但没有实验我们无法进行，我们永远不会知道。

虽然机器学习令人印象深刻，但我们还没有取得任何接近人工通用智能(artificial general intelligence)的成就。人工通用智能指的是对某个主题的真正理解，或实现真正意识或自我意识的人工系统。定义这些术语可能是棘手的、有争议的，甚至不可能。就我个人而言，我从未见过一个正式的意识定义能抓住我对这个概念的直观理解。我怀疑我们永远不会实现强意义上的人工通用智能，即使P = NP。

回到顶部

密码学

虽然我们已经看到在攻击NP问题方面取得了很大的进展，但密码学的许多形式，包括单向函数、安全散列和公钥密码学，似乎都完好无损地保存了下来。一种有效的NP算法，如果存在的话，将会打破所有的密码系统，除了那些理论上信息安全的密码系统，比如一次性垫和一些基于量子物理的密码系统。我们已经看到了许多成功的网络安全攻击，但它们通常源于糟糕的实现、弱的随机数生成器或人为错误，但很少是因为破解了密码。

现在大多数CPU芯片都内置了AES，所以一旦我们使用公钥加密来设置私钥，我们就可以像发送纯文本一样轻松地发送加密的数据。加密技术为区块链和加密货币提供了强大的力量，这意味着人们足够信任加密技术来交换比特。迈克尔·卡恩斯和莱斯利·Valiant²⁴1994年表明学习最小的电路，甚至学习最小的有界层神经网络，可以用来分解数字和破解公钥密码系统。到目前为止，机器学习算法还没有被成功地用于破解密码协议，也没有人期望它们能成功。

---

我怀疑我们永远不会实现强意义上的人工通用智能，即使P = NP。

---

为什么我们在许多其他NP问题上都取得了进展，而加密却能做得这么好?在密码学中，我们可以选择专门设计的难以计算且经过社区测试的问题。其他NP问题一般都是从应用或自然界中来的。它们往往不是最难的案例，而且更容易接受当前的技术。

量子计算似乎威胁到保护我们互联网交易安全的现行公钥协议。肖的算法³⁴能因式分解数字和其他相关的数论计算。这种担忧可以通过几种方式来缓和。尽管量子计算取得了一些令人印象深刻的进展，但我们距离开发出能够处理足够多的纠缠比特、实现肖尔算法的量子机器仍有几十年甚至几个世纪的时间，这种机器的规模可以打破今天的代码。此外，研究人员在开发似乎能抵抗量子攻击的公钥密码系统方面也取得了良好进展。³¹我们将在本文后面详细讨论量子计算。

因式分解还不是np完全的，即使我们没有大规模的量子计算机，数学上的突破也有可能产生高效的算法。无论你对量子的未来持何种观点，拥有多种公钥系统的方法都可能派上用场。

回到顶部

复杂性和摩擦

我们能从计算硬度中得到什么好处?我想到了密码学。但也许宇宙使计算变得困难是有原因的，就像摩擦力一样。在现实世界中，克服摩擦力通常需要消耗能量，但没有能量我们就无法行走。在计算的世界里，复杂性常常会减慢进程，但如果它不存在，我们可能会遇到许多其他问题。P = NP可以让我们，在很多情况下，消除摩擦。

最近的计算进步告诉我们，消除摩擦有时会产生负面的后果。例如，没有人能读懂我们的思想，只能看到我们采取的行动。经济学家有一个术语，“偏好揭示”，试图根据我们的行为来决定我们的欲望。在历史上的大部分时间里，由于缺乏数据和计算能力，这充其量是一种高度不精确的艺术。

今天，我们已经从人们的网络搜索、他们的照片和视频、他们所做的购买、他们访问的地方(虚拟的和真实的)、他们的社交媒体活动等方面收集了相当多的信息。此外，机器学习可以处理这些信息，并对人们的行为做出异常准确的预测。电脑对我们的了解往往比我们对自己的了解还要多。

我们有技术能力戴上眼镜，让你知道你正在看的人的名字、兴趣爱好，甚至政治信仰。复杂性不再为我们提供隐私。我们需要用法律和企业责任来保护隐私。

计算摩擦可以超越隐私。美国政府在1978年解除了对航空公司定价的管制，但要想找到一条航线的最佳价格，需要给多家航空公司打电话或通过旅行社咨询，而旅行社并不总是有动力去寻找最低价格。航空公司靠信誉取胜，有些靠优质服务，有些靠低价。如今，我们可以很容易地找到最便宜的航班，因此航空公司在这个单一的价格维度上投入了相当大的努力，使用计算来优化定价和填满他们的飞机，以牺牲整个飞行体验为代价。

摩擦有助于打击学生作弊行为。我在上世纪80年代上大学时必须回答的微积分问题，现在Mathematica可以轻松解决。对于我的入门理论课程，我在编写作业和考试问题时遇到了麻烦，因为这些问题的答案和答案无法在网上找到。有了GPT-3及其后续版本，甚至作文和编码问题都可以自动生成。当GPT和类似的课程能够回答学生最复杂的问题时，我们该如何激励他们?

股票交易过去是在大场内进行的，交易员们用手势来匹配价格。现在，交易算法会自动调整以适应新的定价，偶尔会导致“闪电崩盘”。机器学习技术导致了决策系统或人脸识别，将社交媒体内容与用户匹配，以及往往大规模的司法判决。这些决策系统有一些好处，但也带来了重大挑战，比如放大了偏见和政治两极分化。^30.这里没有简单的答案。

这些只是许多可能的场景中的一小部分。作为计算机科学家，我们的目标是使计算尽可能地高效和简单，但我们必须保持减少摩擦的成本在我们的头脑中。

回到顶部

量子计算机的力量

随着摩尔定律的局限性越来越明显，计算机研究人员将目光投向非传统的计算模型来实现下一个突破，导致量子计算的研究和应用大幅增长。主要的科技公司，如谷歌、微软和ibm——更不用说一大批初创企业了——已经投入了相当多的资源来开发量子计算机。美国启动了国家量子计划(National Quantum Initiative)，其他国家，尤其是中国，也纷纷效仿。

2019年，谷歌宣布¹它使用了具有53个量子比特的量子计算机来实现“量子霸权”，解决了目前传统计算无法解决的计算任务。虽然有些人质疑这一说法，但我们无疑正处于量子计算新时代的边缘。尽管如此，我们离拥有运行彼得·肖尔的算法所需的数万个量子比特还很远³⁴找出当今机器无法分解的质因数。通常，量子计算被描述为比特所代表的状态数——例如，2⁵³53量子比特机器的状态。这可能表明，我们可以使用量子计算来解决np完全问题，方法是创建足够的状态，例如，检查图中所有潜在的派系。不幸的是，量子算法操纵这些状态的方式是有限的，所有证据都表明量子计算机不能解决np完全问题，^3.超越了格罗弗算法的二次改进。¹⁸

回到顶部

复杂性更新

自2009年的调查以来，我们在对高效计算能力的理解上取得了几项重大进展。虽然这些结果并没有在解决P与NP的问题上取得重大进展，但它们仍然显示出它如何继续激发伟大的研究。

图同构。一些NP问题不愿意被定性为P(有效可解)或NP完全(和小集团问题一样难)。最著名的整数因式分解，我们之前讨论过，仍然需要指数级的时间来求解。对于另一个这样的问题，图同构，我们最近看到了巨大的进展。图同构是指两个图在重新标记之前是否完全相同。以Facebook为例，给定两个1000人的群组，我们能否将一个群组的名字映射到另一个群组，以一种保留友谊的方式?

20世纪80年代的交互证明的相关结果提供了强有力的证据，证明图同构不是np完全的，⁴在实践中，即使是简单的启发式算法，一般也能快速解决这类问题。然而，我们仍然缺乏一个多项式时间的算法，图同构工作在所有的实例。László Babai在2016年取得了突破性的成果，提出了一个图同构的准多项式时间算法。²P的问题是多项式时间运行的，n^k为一个常数k,在那里n就是输入的大小，比如每组的人数。准多项式时间算法在时间上运行n^{（日志n）k}，比多项式时间差一点，但大大优于指数时间(2^nε)，我们期望np完整的问题将需要。

巴巴的证明是组合逻辑学和群论相结合的杰作。尽管让算法在多项式时间内运行需要一些新的突破，但Babai提供了一个重要的理论结果，在P-complete和NP-complete之间的一个最重要的问题上取得了重大进展。

电路。如果NP在一个完整的基上没有小电路(AND, OR, not)，那么P≠NP。虽然80年代有显著的电路复杂度结果，但没有一个接近显示P≠NP。2009年的调查指出，在之前的20年里，在电路复杂性方面没有重大的成果。这种情况又持续了大约一年。1987年,Razborov³²和Smolensky³⁶证明了用与、或、非和模的等深度电路计算多数函数是不可能的_p对于某个固定质数的门p。但对于有Mod的电路，我们能证明的很少₆盖茨。甚至表明NEXP，一个指数时间的NP版本，不能由小的，恒深电路AND, OR, not和Mod计算₆几十年来，盖茨一直开放着。人们认为恒深电路的计算能力较弱。缺乏结果反映了我们在显示计算模型的局限性方面所取得的微不足道的进展。

2010年，瑞恩·威廉姆斯表示³⁹NEXP确实没有这么小的恒定深度电路与Mod₆或任何其他Mod门。他创造了一种新技术，使用满足度算法，比尝试所有的赋值和使用几种复杂工具来达到下界只做得稍微好一点。后来，威廉姆斯和他的学生科迪·默里加强了力量²⁹结果表明，非确定性准多项式时间不具有带模的小等深电路_米任何固定的门m。然而，证明NP不具有任意深度的小电路——这是证明P≠NP所需要的——仍然是遥不可及的。

---

所有证据表明，量子计算机不能解决np完全问题，除了Grover算法给出的二次改进。

---

复杂性反击战?2009年的调查中有一段名为“新希望?”¹³基于代数几何和Ketan mulmulley和Milind Sohoni提出的表示理论，我们讨论了一种新的几何复杂性理论方法来攻击P vs. NP。简而言之，mulmulley和Sohoni试图创建高维多边形，在代数版NP中捕捉问题的力量，并表明它与p的代数属性对应的任何此类多边形具有不同的属性。他们的一个猜想考虑了多边形包含某个表示理论对象的属性。2016年，Peter Bürgisser, Christian Ikenmeyer和Greta Panova⁶说明这种方法不可能成功。

虽然Bürgisser-Ikenmeyer-Panova结果对分离P和NP的GCT方法造成了打击，但它没有将其排除。我们仍然可以根据这些表示理论对象的数量创造出不同的多边形。然而，我们不应该期望GCT方法在近期内解决P vs. NP问题。

回到顶部

不可能的可能性

当我们反思P和NP时，我们看到这个问题有许多不同的含义。有P vs. NP数学问题——正式定义的，顽固开放的，仍然有一百万美元的悬赏。有时候，我们可以通过可计算理论、电路、证明和代数几何等工具来解决P和NP问题。目前，我们还没有一个强有力的方法来解决P对NP问题。从某种意义上说，我们比以往任何时候都更难以解决这个问题。

还有一些NP问题是我们想要或需要解决的。在1976年的经典文本中，计算机与顽固性:np完备性理论指南，¹⁶加里和约翰逊给出了一个例子，一个倒霉的员工被要求解决np完全优化问题。最终，员工找到老板说:“我找不到一个有效的算法，但所有这些名人也找不到。”这表明老板不应该解雇这名员工，因为没有其他员工可以解决这个问题。

在早期的P vs NP中，我们把NP完全性看作是一个障碍——这些都是我们无法解决的问题。随着计算机和算法的发展，我们发现通过结合启发式、近似和蛮力计算，我们可以在许多NP问题上取得进展。在加里和约翰逊的故事中，如果我是老板，我可能不会解雇这名员工，而是建议尝试混合整数编程、机器学习或暴力搜索。我们早已经过了np完全意味着不可能的时代。这只是意味着，可能没有一种算法总是有效和可扩展的。

在我2013年写的关于P和NP的书中，¹⁴我有一章的题目是“美丽的世界”，我想象一个理想化的世界，在这个世界里，一位捷克数学家证明了P = NP，引出了一个非常有效的算法来解决所有NP问题。虽然我们现在没有，也可能永远不会生活在这个理想的世界里——医学的进步，虚拟世界与现实无法区分，学习算法产生新的艺术作品——但P = NP的美妙(或不那么美妙)结果似乎不再遥不可及，而是我们进一步提高计算能力的最终结果。

我们实际上是在完全颠倒P和NP问题的意义。P和NP不代表障碍，而是打开大门，为我们呈现新的方向，向我们展示不可能的可能性。

回到顶部

致谢

感谢Josh Grochow对GCT问题的有益讨论，以及Bill Cook允许我们使用图1中的图片。我也感谢Josh和那些匿名的评审员帮助我们改进展览。本文中的一些材料改编自作者的博客。¹⁵

数字观看作者对这部作品的独家讨论通信视频。//www.eqigeno.com/videos/fifty-years-of-p-vs-np

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2022 ACM股份有限公司

---

没有发现记录