核心不雅观点：
1. 至2021年，P/NP问题已经50岁了，但其办理方案仍遥不可及。只管算法与硬件的卓越进步使我们可以办理许多NP完备问题，但在密码系统的破解方面仍进展甚微。
2. 随着我们持续地在机器学习以及以数据为中央的打算领域取得激动民气的进步，P/NP问题向我们供应了一个宝贵的视角，去理解在未来的机器学习领域什么是可能的，什么是不可能的。
3. 虽然P/NP问题一开始涉及繁芜问题的打算求解，但如今我们将其视为绘制这个领域未来发展蓝图的一种方法。
（编者注：正文内参考文献序号为原文标注；原文揭橥于2022年。）
撰文 | Lance Fortnow（伊利诺斯理工学院打算机学院教授）
翻译 | 许钊箐
1971年5月4日，数学家、打算机科学家史蒂夫·库克（Steve Cook）在他的论文《定理证明过程的繁芜性》（The Complexity of Theorem Proving Procedures）中向众人先容了P/NP问题。如今，50多年过去了，全天下仍在考试测验办理这一问题。在2009年，我在《ACM通讯》（Communications of the ACM）杂志上揭橥综述文章《P/NP问题的现状》，磋商过这一话题[13]。
自2009年那篇文章揭橥以来，P/NP问题及其干系的理论并没有显著的进展，但是打算领域无疑发生了巨变。云打算的发展促进了社交网络、智好手机、零工经济、金融科技、空间打算、在线教诲等领域的进步，并且大概个中最主要的是数据科学与机器学习的崛起。在2009年，市值排名前十名的公司中仅仅只包含一家大型科技公司：微软。而截止至2020年9月，市值排名前七名的公司是：苹果（Apple）、微软（Microsoft）、亚马逊（Amazon）、谷歌（Alphabet）、阿里巴巴（Alibaba）、脸书（Facebook）、腾讯（Tencent）[38]。在此期间，美国打算机科学专业毕业生的数量增加了两倍多[8]，但仍远远不能知足岗位的需求。
在本文中，我选择通过P/NP问题的视角来看待打算、优化以及机器学习领域的进展，而不仅仅是大略修正或更新2009年文章的内容。我们将关注这些进展是如何使我们更靠近P=NP的天下，P/NP问题至今仍存在的局限性，以及已经呈现的新的研究机会。特殊地，我谈判量我们是如何走向一个我称之为“Optiland”的天下，在那里我们险些可以奇迹般地得到P=NP的许多优点，并且同时避免一些缺陷，比如冲破密码学的干系理论。
作为一个开放的数学难题，P/NP问题至今是个中最主要的之一；它被列入克莱数学研究所的千禧年大奖难题之一[21]（该组织为个中每一个问题的求解供应100万美元的奖金）。在本文的末了，我也将陈述一些前沿打算机科学的干系理论结果。虽然这些结果没有让我们更靠近于办理P/NP问题，但它们向我们展示了对付P/NP问题的思虑仍旧推动了该领域浩瀚的主要研究。
P/NP 问题
是否存在300个Facebook用户彼此之间都是好友的关系？你将如何为这个问题供应一个解答？假设你在Facebook公司事情，可以访问公司所有数据，理解哪些用户是好友关系。你现在须要设计一个算法来探求彼此都是好友并且人数足够多的朋友群体（Clique）。你可以先考试测验搜索所有知足条件的300人朋友群体，但由于实际人数过多，无法全部搜索。你也可以选择一些更明智的方法，比如先考试测验搜索一些小型朋友群体，之后再小的群体合并为更大的群体，但你会创造你所做的彷佛都不起浸染。事实上，没有人知道比遍历所有朋友群体明显更快的搜索方法，同时我们也不知道更快的方法是否不存在。
这基本上便是P/NP问题。NP代表我们可以高效考验其解答的问题。如果我奉告你有300人可能形成了一个知足条件的团体，你可以相对较快地考验他们彼此之间形成的44850对用户是否都是好友关系。上文的分团问题（Clique problem）便是一个NP问题。而P则表示我们可以高效地找到解的问题。对付分团问题，我们不知道它是否在P问题这个凑集中。或许会令你惊异的是，分团问题有一个被称为NP完备（NP-complete）的性子——即当且仅当P=NP时，我们才可以高效地办理分团问题。许多其他问题也有这一性子，比如三着色问题（一副舆图能否可以仅被三种颜色着色使得任意相邻的两个国家拥有不同的颜色？），旅行商问题（在浩瀚的城市中找到一个最短路线，使得贩子访问每座城市一次并回到初始的位置），以及其他成千上万的问题。
严格地来说，P表示“多项式韶光”（polynomial time），对应一类求解韶光因此输入长度为自变量的固定多项式的问题。而NP表示“非确定性多项式韶光”（nondeterministic polynomial time），对应一类非确定性图灵机可以不可思议地选择出最佳答案的问题。在本文中，读者可以把P和NP大略地看作可高效求解的问题以及可高效验证的问题。
如果读者希望对付P/NP问题的主要性有更深入的非专业谈论，可以阅读我2009年的综述文章[13]或者我在2013年基于这篇综述文章写作的科普书本[14]。对付更专业的先容，由迈克尔·加里（Michael Garey）和大卫·约翰逊（David Johnson）[16]在1979年创作的专著对付须要理解哪些问题是NP完备问题的读者非常得当。这本专著至今仍旧是这方面的宝贵参考资料。
为什么我们现在评论辩论P/NP问题？
1971年一个周二的下午，在美国俄亥俄州谢克海茨市的斯托弗萨默塞特酒店，史蒂芬·库克（Stephen Cook）在ACM打算理论专题研讨会上向与会者展示了他的论文，他证明了布尔表达式可知足性问题（Boolean Satisfiability Problem）是NP完备的，并且证明了重言式问题（Tautology）是NP困难（NP-hard）的[10]。这些定理也表明，重言式问题是一个不在P凑集中不错的候选，并且我认为花费相称大的精力来考试测验证明这个猜想是值得的。这样的证明将会是繁芜性理论的重大打破。
与一个数学观点“约会”险些总是一个寻衅，历史上大概还有很多P/NP问题可能的出身韶光。算法和证明的基本观点可以被追溯到古希腊期间，但据我们所知，P/NP这样一样平常性的问题他们从未考虑过。高效打算与非确定性的理论根本是在20世纪60年代发展起来的，而P/NP问题在此之前就形成了，只是我们不知道详细韶光而已。
在1956年库尔特·哥德尔（Kurt Gödel）写给约翰·冯·诺伊曼（John von Neumann）的一封信中，哥德尔实质性地描述了P/NP问题。目前我们尚不清楚，当时身受癌症侵袭的冯·诺伊曼是否阅读了这封信。直到1988年，这封信才被人们创造，并广为传播。而P/NP问题是直到理查德·卡尔普（Richard Karp）1972年揭橥论文[23]指出大量著名组合问题（包括分团问题、三着色问题、以及旅行商问题）是NP完备的之后才真正成为一种征象。1973年，当时在苏联的列昂尼德·莱文（Leonid Levin）在其1971年独立研究的根本上揭橥了一篇论文，个中定义了P/NP问题[27]。而当莱文的论文传到西方的时候，P/NP问题已经成为打算领域最主要的问题了。
乐不雅观之地（Optiland）
在1995年的一篇经典论文中[20]，拉塞尔·因帕利亚佐（Russell Impagliazzo）描述了对付P/NP问题拥有不同程度可能性的五个天下：
1. 算法天下（Algorithmica）：P=NP或者某种理论上的等价，比如NP问题的快速随机算法。
2. 启示天下（Heuristica）: 在最坏的情形下NP问题很难求解，但是常日情形下求解是随意马虎的。
3. 悲观天下（Pessiland；译者注：引申自拉丁语悲观主义pessimus）：我们可以轻易地构建难以求解的NP问题，但是很难构建我们知道解答的NP问题。这是所有可能性中最坏的，由于在这个天下中，我们既不能在常日情形下办理困难的问题，也不能由这些问题的难度得到任何明显的加密上风。
4. 单向加密天下（Minicrypt）：单向加密函数存在，但是我们没有公开密钥加密算法。
5. 加密狂欢天下（Cryptomania）: 公开密钥加密是可能的，也便是说，双方可以通过公开的信道交流加密信息。
这些对应不同情形的不同天下特意没有被正式定义。根据我们对付P/NP问题的理解，它们表明了未知的各种可能性。人们常日认为（不是全体统一地），我们生活在可以“加密狂欢”的天下里。
因帕利亚佐从P/NP的理论中总结出：“鱼与熊掌不可兼得（You can't have it all）”。我们可以求解困难的NP问题，或者可以拥有密码学，两者必有其一，但不会共存。不过，或许我们正在前往一个现实中的“乐不雅观之地”（Optiland；译者注：与pessiland对应，引申自Optimum）。机器学习和软件与硬件优化的进展，使我们能够对付此前长期被认为是困难或不可能的问题取得进展，比如语音识别与蛋白质折叠等问题，并且在大多数情形下我们的加密协议仍旧是安全的。
在我2009年的综述文章[13] “如果P=NP会怎么样？”章节里，我当时写道，“通过利用奥卡姆剃刀原则（Occam’s razor），学习变得随意马虎了——我们只需探求与数据同等的最大略的方法”。近乎完美的视觉识别、措辞理解、翻译，以及所有其他的学习任务都变得随意马虎办理。我们也将更好地预测景象、地震以及其他自然征象。
如今，我们可以通过面部扫描来解锁智好手机，通过讯问手机问题得到常日较为空想的回答，也可以将我们的问题翻译为另一种措辞。智好手机会吸收关于景象和极度景象的警报，而其预测能力比我们十几年前想象的要好得多。同时，除了小长度密钥加密会受到类似暴力破解的攻击之外，密码学理论基本没有被撼动。接下来，让我们来看一看打算、优化以及学习领域最近的进展是如何将我们领入“乐不雅观之地”的。
困难问题的求解
2016年，比尔·库克（Bill Cook, 与前文中的史蒂夫·库克没有关系）和他的同事们决定欢迎这项寻衅[9]：如何利用最短的路程到访英国的每一家酒吧？他们列出了24727家酒吧的名单，并确定了末了的酒吧旅行路线——一次总长度45495239米的徒步旅行。这一间隔比绕地球一圈还要长一些。
实际上，库克对该问题做了一些简化：他忽略了一些酒吧使得该问题有一个得当的规模。在一些英国媒体进行宣布[7]之后，许多人抱怨名单中没有他们最爱的酒吧。因此库克团队重新整理了一份包含49687家酒吧的名单，而新的行程长度是63739687米（见下图）。与之前的路径比较，人们只须要多走40%的路程，便能到访数量是之前两倍多的酒吧。这个酒吧旅行的问题与旅行商问题（最著名的NP完备问题之一）是等价的。到访49687家酒吧所有可能路线的数量大约是“3后面随着211761个0”。当然库克的电脑不会遍历所有路线，他们利用了各种优化技能。更令人印象深刻的是，这份路线还附带一份基于线性方案对偶性的最优性证明。
穿过49687家英国酒吧的最短路线 图片来源：math.uwaterloo.ca/tsp/uk
库克团队也承担了一个更大的任务——探求一条穿越200多万恒星的最短路径，个中恒星之间的间隔可以被打算。他们得到的路线总长度为28884456秒差距（译者注：1秒差距约为3.26光年），和理论最佳值比较只有683秒差距的差别。
除了旅行商问题，我们在求解布尔可知足性问题和稠浊整数方案问题（Mixed-integer programming question）领域也取得了重大进展——一种线性方案方法的变体，个中一些变量（不一定是全部）必须是整数。通过利用高度精髓精辟的启示式方法、高速处理器、专业硬件以及分布式云打算，人们基本已经可以办理实践中涌现的具有数以万计的变量和数十万乃至上百万的约束的问题。
面对须要求解的NP问题，人们常日会将问题转述为布尔可知足性问题或稠浊整数方案问题，进而利用最好的求解器求解。这些工具已经被成功地运用在电路与编码的验证与自动化测试、打算生物学、系统安全、产品与包装设计、金融交易中，乃至用于求解困难的数学问题。
数据科学与机器学习
如今，任何《ACM通讯杂志》的读者和其他大多数人都不会忽略机器学习带来的变革性影响，尤其是通过神经网络实现的机器学习。利用人工神经元（笼统地讲，打算加权阈值函数）实现建模打算的观点可以追溯到20世纪40年代沃伦·麦卡洛克（Warren McCulloch）和沃尔特·皮茨（Walter Pitts）[28]的研究。在20世纪90年代，约书亚·本希奥（Yoshua Bengio）、杰弗里·辛顿（Geoffrey Hinton）和杨立昆（Yann LeCun）[26]提出了反向传播等算法，为多层神经网络学习演习的发展奠定了根本。更快、更广泛的分布式打算、专业硬件和海量数据也帮助并推动了机器学习的发展，使得它可以非常出色地完成浩瀚原来须要人类完成的任务。打算机协会（the Association for Computing Machinery，ACM）也为本希奥、辛顿和立昆付与了2018年的图灵奖，以表彰他们的工为难刁难人类社会产生的深远影响。
那么，机器学习与P/NP问题有什么联系？（在本节中，当我们提及P=NP，它表示所有的NP问题在实践中都有干系的高效算法。）奥卡姆剃刀原则指出，“如无必要，勿增实体”，或者说，最大略的阐明可能才是精确的。如果P=NP，我们可以利用这一思想来建立一个强大的学习算法：找到一个与数据同等的最小的回路。但即便可能没有P=NP这个结论，机器学习也可以近似地实现这种方法，从而授予了神经网络惊人的能力。然而，神经网络不太可能是那个“最小的”回路。如今利用深度学习技能演习的神经网络每每构造是固定的，其参数与网络中的权重有关。为了拥有足够的表达能力，人们常日须要设置数百万乃至更多的权重参数。而数量浩瀚的参数限定了神经网络的能力：它们可以很好地进行面部识别，但是却无法根据示例来学习如何进行乘法运算。
通用分布（Universal distribution）和GPT-3 让我们考虑任意长度二进制字符串的分布。只管均匀分布是明显不合理的，但是我们是否可以构建分布使得任意相同长度的字符串拥有相同的概率？实际上，有些字符串确实会比其他的更主要。比如，π的前100万位数字比随机天生一个100万位数字更故意义。因此或许你会希望给更故意义的字符串设置更高的概率。实现这一目标的方法很多，而实际上存在一个靠近于任何其他可打算分布的通用分布（读者可以参考科尔什赫等人的文章[25]）。通用分布与学习演习有很大的联系，例如，任意以小偏差率学习这种分布的算法将可以学习所有可以打算的分布。可惜的是，即便P=NP，通用分布也是不可打算的。不过，如果P=NP，我们仍旧可以得到一些有用的东西——我们可以创建一个可高效打算的分布，使得它对付其他可高效打算的分布是通用的。
我们能从机器学习中得到什么？以GPT（Generative Pre-trained Transformer，天生式预演习转换器）为例，特殊是2020年发布的GPT-3[5]。GPT-3从尽可能多的书面语料库中提取了4100亿个标记，进而演习了1750亿个参数。它可以回答问题，可以根据提示书写文章，乃至可以天生代码。只管它还有漫长的优化之路要走，但是它已经可以像人类一样创造内容，并因此受到好评。我们可以把GPT-3看作是一种分布，并考虑算法输出对应的概率——即一个弱版本的通用分布。如果我们以一个给定的前缀限定通用分布，那么它就供应一个由该前缀提示的随机样本。GPT-3也可以基于这样的提示，无需进一步演习就能处理极大范围的干系领域知识。随着这方面研究的进展，我们也将越来越靠近一个通用度量标准并从中实现内置式学习：基于给定高下文天生一个随机的例子。
科学与医药 在科学天下，我们已经通过大规模仿照取得了浩瀚进展，比如探索核聚变反应。研究者们利用一种科学方法的范式：首先对付物理系统建立假设；然后利用模型进行预测；再用实验仿照考验该预测，而不是直接实现核聚变反应。如果测试结果与预期不同，再修正或推翻这个模型并重复以上的过程。
在我们拥有一个有说服力的模型之后，我们可以在现实反应堆中进行一些昂贵的实验测试。如果P=NP，像上文提及的，我们可以利用奥卡姆剃刀理论来建立假说——找到一个与数据同等的最小回路。机器学习的技巧可以紧接着沿着这个思路自动地创建假设。不管数据是来自于仿照、实验还是传感器，机器学习都可以创建出匹配数据的模型。然后我们可以利用这些模型来进行预测，并像前文提到过的那样考验做出的预测。
只管机器学习可以帮助我们找到未创造的假设和模型，但所得到的结果未必是精确的。我们常日可以接管有95%置信水平的假设（这意味在20个不合格的假设中，有一个可能会被接管）。机器学习与数据科学的工具为我们天生假设的同时，也带来了却果不符合事实的风险。医学研究职员，特殊是试图办理癌症等疾病的研究职员，常常碰着算法上的阻碍，由于生物系统极其繁芜。我们知道DNA构成一种编码，它描述了我们的身体如何形成以及身体不同部分的功能，但我们对其运作事理知之甚少。
2020年11月30日，谷歌的DeepMind公司发布了AlphaFold——一种基于氨基酸序列预测蛋白质构造的新算法[22]。AlphaFold的预测准确度险些达到了人工实验的水平，即通过实验构建氨基酸序列并测试其天生的蛋白质构造。虽然关于DeepMind是否真的“办理”了蛋白质折叠的问题仍存争议，并且现在便评估其影响力还为时过早，但从长远来看，它为我们供应了一个新的数字化工具来研究蛋白质，理解它们是如何相互浸染，并学习如何设计蛋白质来对抗疾病。
P/NP之外：象棋与围棋 NP问题就像解谜游戏。数独问题便是NP完备的：在一个任意大小的宫格上，给定一些初始数字，然后求解别的空格中数字。但是对付两位玩家轮流执子的回合制游戏，比如象棋和围棋，如果我们想知道谁会在给定棋局下得胜，情形又会怎么样呢？事实上，即便是P=NP，我们也未必可以找到完美的棋类算法。我们不得不考虑对付黑子的每一步，白子都可以走出得当的一步，并不断循环直到白棋胜利。而设计这种交替的算法仅仅依赖P=NP是不足的。这一类游戏的算法设计被称为PSPACE-hard——在没有韶光限定下，利用合理的存储容量进行打算是困难的。根据详细的规则设定，象棋和围棋的算法设计会更有难度。（感兴趣的读者可以阅读德迈纳与赫恩的文章[11]。）
不过，这并不虞味着在假设P=NP的条件下，我们不能找到一个好的棋类算法。你可能做出一个大小得当的高效打算机程序，使其优于所有比它体量略小的高师法式。另一方面，即便没有P=NP这一假设，打算机在棋类方面已经足够强大。在1997年，IBM的超级电脑“深蓝”击败了当时的国际象棋天下冠军加里·卡斯帕罗夫（Gary Kasparov），然而在当时，即便是与有实力的业余选手的对决，围棋程序也难以取胜。在这之后，机器学习在打算机游戏的算法设计方面取得了巨大的进步。让我们直接跳过这段悠久的历史，来看看2017年DeepMind开拓的AlphaZero[35]。
AlphaZero利用了一种被称为蒙特卡洛树搜索（MCTS）的技能——让双方玩家随机地落子从而决定最佳的棋路方案。AlphaZero利用深度学习来预测棋局的最佳分布，以优化利用MCTS得胜的机会。虽然AlphaZero并不是第一个利用MCTS的程序，但是它没有任何内置策略或者访问之前的棋类数据库——它仅仅假设了游戏的规则。这也使得AlphaZero在国际象棋和围棋上都表现得出色，这两种游戏除了交替回合制和固定大小的棋盘之外截然不同。DeepMind最近进一步地研究了MuZero[33]——它乃至没有完全的规则，仅仅有一些棋盘位置的表示，一系列符合规则的落子，以及哪些情形是赢、输或者平局。现在我们已经明白，在国际象棋和围棋中，纯粹的机器学习可以很轻易地击败人类或者其他算法。而人为地干预只会妨碍它。对付象棋和围棋这类游戏，即便P=NP不敷以办理这类问题，但机器学习却可以取获胜利。
可阐明的人工智能 很多机器学习算法彷佛已经都运行得很好，但是我们却不理解为什么。如果你去不雅观察为了语音识别而演习的神经网络，你常日会难以理解它为何做出这样的选择。我们为什么要关心这个问题呢？以下是一些缘故原由：
1. 置信：我们如何知道神经网络运行精确？除了检讨输入和输出，我们不会做其他任何的剖析。不同的运用处景会有不同的置信水平：Netflix推举了一部水平不高的电影没什么关系，但如果是自动驾驶的汽车选择了一个缺点的转弯，结果就很严重。
2. 公正：有很多例子表明，通过数据演习的算法受到了数据中故意或无意的偏差的影响。如果我们不理解程序，我们如何创造这些数据中的偏差？
3. 安全：如果利用机器学习来监管安全系统，我们将不知道哪些漏洞仍旧存在，特殊是当我们的敌手是不断变革的时候。但如果我们理解代码，我们就可以创造并修补安全漏洞。当然，如果敌手得到了代码，他们也可以创造漏洞。
4. 因果关系：目前我们最多只能检讨机器学习算法是否与我们想要的输出类型干系。理解代码可以帮助我们理解数据中的因果关系，从而在科学与医学方面取得新的进步。
如果P=NP，我们会得到一个更好的情形吗？如果我们有一个NP完备问题的快速算法，你可以将其用于匹配问题或旅行商问题，找到可能的最小回路，但你不会知道为什么这个回路是对的。另一方面，我们想要一个可阐明算法的缘故原由是我们希望可以理解它的性子，但如果P=NP，我们可以直接导出这些性子。现在研究可阐明的人工智能会议呈现出来，例如ACM FAccT会议。
机器学习的局限性 虽然在过去十年中，机器学习已经展现了许多令人惊奇的结果，但很多系统还远未达到完美的水平，在大多数运用处景中，人类仍旧更胜一筹。人们也将连续通过新的优化算法、数据网络与专业硬件来提高机器学习的能力。不过，机器学习彷佛确实有其局限性。正如我们上文提到过的，机器学习让我们一定程度的靠近P=NP，但却永久无法替代P=NP——机器学习在密码破解方面进展甚微，我们也将在本文后面看到这一点。
机器学习彷佛无法学习大略的算术——例如对大量的数字求和或者大数之间相乘。人们可以想到将机器学习与符号运算的数学工具结合起来。然而，只管在定理证明方面我们取得了一些令人瞩目的进展[19]，但这与我们期待中的实际科研任务仍间隔迢遥，即选取一篇科研文章，文中证明还未正式完成，利用AI系统补充细节并考验证明。
而P=NP将使这些任务变得大略，或者至少易于处理。机器学习在面对不属于其演习分布的任务时可能表现不佳。但这可能是概率较低的极度情形，例如演习数据中并未得到很好代表某个种族的人脸识别；或者可能是一种对抗性的考试测验——通过对输入进行眇小的变动来强行得到不同的输出，比如把停车标志修正几个像素，从而让算法将其识别为一个限速标志[12]。深度神经网络算法可能有数百万个参数，因此它们在分布之外的泛化效果可能不理想。如果P=NP，我们可以得到最小尺寸的模型从而有望实现更好的泛化，但如果没有相应的实验，我们永久也无法验证。
只管机器学习令人印象深刻，但我们还没有得到任何靠近于通用人工智能的东西——这个术语指的是对付一个主题有真正的理解，或是实现真正的意识或自我认知的人工系统。定义这些术语可能是棘手的、有争议的，乃至是不可能的。于我个人而言，我从未见到过一个关于意识的正式定义，能够表示我对付意识的直不雅观认识。我疑惑纵然P=NP，我们也永久无法实现强意义下的通用人工智能。
密码学
虽然我们在办理NP问题方面取得了很大进展，但是密码学的多种理论，包括单向函数（one-way functions）、安全散列算法（secure hashes）以及公钥密码学彷佛都无缺无损。如果NP问题存在一个高效的算法，那么除了那些在信息学上安全的密码系统，比如一次性密码簿和一些基于量子物理学的密码系统，其他所有密码系统都会被破解。我们已经见证了很多成功的网络安全攻击，但它们常日源于糟糕的代码漏洞、很弱的随机数天生器或者人为疏漏，很少是由于密码学理论的问题。
现在大多数CPU芯片都内置了AES（Advanced Encryption Standard），因此一旦我们利用了公钥加密系统设置私钥，我们就可以像发送普通文本一样轻松地发送加密后的数据。加密技能为区块链和加密货币的发展供应了动力，这意味着人们对付加密技能的信赖足以让他们乐意把货币换成比特。迈克尔·卡恩斯（Michael Kearns）和莱斯利·瓦利安特（Leslie Valiant）在1994年证明[24]，如果可以学习到最小的回路，乃至只是学到了最小的有界层的神经网络，那么它们就可以被用来分解质因数并破解公钥加密系统。而到目前为止，机器学习算法还从未成功破解过加密协议，不过也没有人期望机器学习算法可以成功。
为什么我们在许多其他NP问题取得了进展，而加密系统仍可以表现良好？在密码学中，我们可以选择问题，特殊是可以将其设计成难以打算并可被广为测试的。而其他的NP问题常日来自运用问题或自然界。它们每每不是最困难的，也更随意马虎折服于当下技能。
量子打算彷佛威胁着当下保护我们互联网交易的公钥加密协议。秀尔算法（Shor’s algorithm）[34]可以进行质因数分解与其他数论打算。这种忧虑可以通过几种办法来缓和。只管量子打算取得了一些令人印象深刻的进展，但要开拓出能处理足够多纠缠比特的量子打算机，从而在一定规模上实现秀尔算法，我们可能仍须要几十年乃至几个世纪的韶光。此外，研究者们也在开拓可抵抗量子攻击的公钥密码系统并取得了一定的进展。更多量子打算内容我们将在后文详细谈论。
我们不知道因式分解问题是否是NP完备的，以是即便我们没有大规模的量子打算机，数学上的打破也有可能会带来高效的算法。但无论你对量子领域的未来有什么样的意见，如果拥有多种方法来优化公钥加密系统，它们可能都会派上用场。
如摩擦力般的繁芜性
我们可以从打算繁芜性中得到什么？此时，密码学可能会从你的脑海浮现。但或许就像存在摩擦力一样，宇宙使得某些打算很困难是有缘故原由的。在物理天下中，战胜摩擦力常日以花费能量为代价，但是如果没有摩擦力，我们寸步难行。在打算天下中，错综繁芜的打算一样平常会使打算过程缓慢而低效，但如果没有繁芜性，就像没有摩擦力一样，我们也会有很多其他的问题。而P=NP在很多情形下，会让我们肃清“摩擦力”。
打算领域的最新进展表明，肃清“摩擦力”有时会产生负面影响。例如人们不能直接阅读别人思想，只能看到其采纳的行动。经济学家有一个术语，“偏好揭示”（preference revelation），旨在根据人们的行为来确定其偏好。在过去，由于缺少数据与足够的算力，这一领域一贯被认为最多只是非常禁绝确的一种艺术。
而如今，我们已经网络到了相称可不雅观的数据——来自人们的网络搜索、相片与视频、网购记录、虚拟与现实天下中的访问记录、社交媒体上的活动等等。而且，机器学习可以处理这些繁杂的信息，并对人们的行为做出非常精确的预测。如今，打算机比我们更理解我们自己。
我们乃至已经有足够的技能制作一副眼镜，戴上它就可以让我们理解对面人的名字、兴趣与爱好，乃至其政治态度。因此这种信息上的繁芜性已不再授予我们隐私。人们须要依赖法律和企业任务来保护隐私。
打算上的“摩擦力”不仅表示在隐私这一方面。在1978年，美国政府解除了对航空公司的定价牵制，但如果想要找到一条航线的最佳价格，人们每每须要给多家航空公司打电话咨询，或者通过旅行社代理购票，当然旅行社也并不总是有动力去探求最低的价格。因此航空公司致力于打造荣誉，一些公司侧重优质的做事，另一些公司可以供应更低的价格。本日，我们可以很随意马虎地找到最便宜的航班，因此航空公司在价格这个单一维度上投入了相称大的努力，他们通过打算优化定价并以捐躯翱翔体验的代价来安排座位。
这种“摩擦力”在以前也有助于打击学生的作弊行为。在上世纪80年代，我读大学时必须打算作答的微积分问题，现在已经可以被Mathematica软件轻松办理。在我的入门理论课程中，我在为学生准备作业与考题的时候碰着了麻烦——答案都可以在网上找到。随着GPT-3和其后续版本能力日益强大，乃至连论文与代码都可以自动天生，如果GPT这类的工具已经可以办理对付学生来说最繁芜的问题，我们要如何引发学生？
股票交易过去是在现场进行的，交易员用手势来进行价格匹配。如今，交易算法自动地调度以适应新的价格，偶尔会导致价格瞬间暴跌。机器学习技能的发展已经引领了决策系统、人脸识别，将社交媒体内容与用户，还有法律讯断进行大规模匹配。这些决策系统带来了一些好的改变，但也为我们带来了重大的寻衅，比如放大偏见、加剧政治上的两极分解[30]。本文不详细磋商这个话题。
以上提到的这些只是许多可能的场景中的一小部分。作为打算机科学家，我们的目标是使打算尽可能的高效和大略，但我们也必须牢记减少“摩擦力”的代价。
量子打算机的能力
随着摩尔定律的极限越来越明显，打算机科学家们已经将目光投向非传统的打算模型以追寻下一阶段的打破。这促进了量子打算理论与运用的发展。大型科技公司，如谷歌、微软和IBM，还有一大批初创公司，都已在量子打算机开拓上投入了大量资源。美国已经启动了国家量子操持（National Quantum Initiative），其他国家，尤其是中国，也都加入了这一行列。
2019年，谷歌[1]宣告其利用了一台拥有53个量子比特的量子打算机实现了“量子遥遥领先”，办理了当前传统打算无法办理的打算任务。只管有些人质疑这一说法，但我们确实正处在量子打算新时期的边缘。然而我们还远没有达到实现皮特·秀尔（Peter Shor）算法[34]所须要的数万个量子比特的水平，从而办理当今打算机打算质因数分解问题。常日来说，量子打算被描述为由比特表示的状态数，比如53量子比特的机器有253个状态。这彷佛表明，我们可以利用量子打算通过创建足够多的状态来办理NP完备问题——例如，在一个图构造中，考验所有可能知足条件的团体。可惜的是，量子算法操控这些状态是受限的，而且所有的证据都表明，除了由格罗弗（Grover）算法[18]给出的二次加速改进，量子打算机无法办理NP完备问题[3]。
繁芜性的进展
自2009年我揭橥那篇综述文章之后，我们在理解高效打算能力方面取得了几项重大进步。虽然这些结果对付办理P/NP问题没有带来显著的进展，但依旧展现了它们是如何连续启示后续精良研究的。
图同构：一些NP问题可能既不是P（高效可解），也不是NP完备的（像分团问题一样难）。个中我们前文提及的最著名的质因数分解问题，仍旧须要指数级的韶光来求解。而对付另一个类似的问题——图同构问题，我们最近见证了激动民气的进展。图同构指的是在重新标号的意义下，两个图是否相同。以Facebook为例，给定两个千人的群组，我们能否将名字在两个群组中以一种办法相互对应，并保持人们之间的好友关系？
20世纪80年代揭橥的与交互性证明干系的结果为证明图同构不是NP完备的供应了强有力的证据[4]。而且即便是大略的启示式算法常日也可以快速办理这类问题。可是我们仍旧缺少一个适用于所有情形的多项式韶光的图同构算法。对付该问题，拉斯洛·巴拜（László Babai）
在2016年取得了打破性成果[2]，他提出了一种图同构的拟多项式韶光的算法。
巴拜的证明是一份将组合学与群论结合的精彩事情。只管让算法在多项式韶光内运行结束仍须要很多新的打破，但巴拜给出了一个主要的理论结果，是P与NP完备之间最主要问题之一的重大进展。
电路设计：如果在完备的基（与门、或门、非门）下，小型电路不能求解NP问题，则P≠NP。虽然上世纪80年代有很多关于电路繁芜度的研究成果问世，但它们都没能靠近于证明P≠NP。2009年的综述文章指出，在此前的20年里，电路繁芜性领域没有取得新的重大成果。这种情形一贯持续到2010年。1987年，拉兹波洛夫（Razborov）[32]和斯莫伦斯基（Smolensky）[36]证明了对付固定素数p对应的常数深度电路——由取余电路（Modp）、与门、或门、非门电路组成——是不可能打算大多数函数的。不过，如果是有6对应的取余电路（Mod6），存在少量的一些证明事情。但纵然是证明NEXP（一种NP的指数韶光版本）不能被常数深度的、由与或非门电路以及6对应的取余电路组成的小型电路打算这一问题，其仍在几十年中未被办理。因此常数深度的电路被认为在打算上能力很弱。在这方面事情的缺少也反响了我们在阐释打算模型局限性这一领域取得的进展十分有限。
在2010年，瑞恩·威廉姆斯（Ryan Williams）[39]证明了NEXP确实不能被常数深度、由6对应的取余电路或任意其他取余电路的小型电路打算求解。他布局了一种新技能，运用了可知足性算法。这种算法比考试测验所有赋值并利用几种繁芜工具来得到下界要好一些。后来，威廉姆斯和他的学生科迪·默里（Cody Murray）[29]在此结果上更进一步，证明了即便是不愿定的拟多项式韶光的算法，也不存在对应的常数深度的、带有固定m对应的取余电路（Modm）的小型电路。然而证明不存在任意深度的小型电路可以求解NP问题（这正是证明P≠NP所须要的）仍旧遥不可及。
繁芜性的反击：在2009年的综述文章中，有一节题为“新希望”[13]。在这一节中，我们基于克坦·穆穆利（Ketan Mulmuley）和米林德·索霍尼（Milind Sohoni）提出的代数几何与表示理论，谈论了一种新的几何繁芜性理论来攻破P/NP问题。简而言之，穆穆利和索霍尼试图布局高维多边形，以表示代数形式的NP问题的性子，并表明它具有任意与P问题的代数性子相对应多边形不同的性子。他们的猜想之一因此为多边形包含某种表示论的构造。然而在2016年，彼得·布尔吉瑟（Peter Bürgisser），克里斯蒂安·艾肯迈尔（Christian Ikenmeyer），和格蕾塔·帕诺娃（Greta Panova）[6]证明这种方法不会成功。
只管布尔吉瑟、艾肯迈尔、与帕诺娃的事情否定了几何繁芜性理论（GCT）区分P与NP问题的可能，人们仍旧有可能根据表示论构造的数量布局不同的多边形。只不过我们不再该当期待GCT理论可以在不久的将来办理P/NP问题。
不可能的可能性
当我们思考P/NP问题时，我们创造它有许多不同的含义。P/NP是正式定义的、永劫光悬而未决、仍有百万美元悬赏的一个数学问题。在本文中，我们看到通过可打算性理论、电路设计、证明和代数若干好多么工具试图办理P/NP问题的努力。目前我们还没有一种强有力的方法办理P/NP问题。乃至从某种意义上说，我们到办理这个问题的间隔比以前任何时候都要远。
还有一些NP问题是我们希望或须要办理的。在1976年的经典文献《打算机与难解性：一本NP完备性理论的指南》中[16]，加里（Garey）与约翰逊（Johnson）举了一个例子：一位晦气的员工被哀求办理一个NP完备的优化问题。末了这位员工找到老板说：“我找不到一个高效的算法，但这天下上的天才名流也一样找不到。“言外之意是老板不应该开除这位员工，由于雇佣其他人也无法办理这个问题。
在P/NP问题的研究早期，我们将NP完备性看作一种障碍——这些问题是我们无法办理的。但随着打算机与算法的发展，人们创造通过启示式算法、近似算法和暴力打算的结合，我们也可以在NP问题上取得进展。在加里和约翰逊的故事中，如果我是老板，我不会开除这位员工，而是建议考试测验利用稠浊整数方案、机器学习或者暴力搜索等方法。NP完备意味着不可能的时期已经由去了。现在NP完备仅仅意味着可能没有一种算法可以永久有效和可扩展。
在我2013年终于P/NP问题的书中[14]，有一章名为“俏丽的天下”。在这一章中，我想象了一个空想化的天下：一位捷克数学家在这个天下中证明了P=NP，从而得出一个对付所有的NP问题都非常高效的算法。只管我们现在没有，也很可能永久不会生活在这样空想的天下，但是随着我们在打算上一步一步地提高，我们已经实现了很多医学进步，打造出与现实难以区分的虚拟天下，发明动身明新艺术作品的机器学习算法，P=NP所带来的美妙或没那么美妙的结果彷佛不再遥不可及。
我们正走在险些完备颠覆P/NP问题的意义的道路上。与其将其认为是一种障碍，不如将P/NP问题看作一扇为我们指引方向，展现不可能中的可能性的大门。
致谢
感谢乔希·格罗乔（Josh Grochow）与我对GCT问题非常有帮助的谈论，以及库克许可我们利用干系图片。同样感谢乔希以及审稿人对付本文的建议与帮助。本文的一些材料改编自作者的博客。
参考文献
[1] Arute, F., Arya, K., Babbus, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boxio, S., Brandao, F.G.S.L., Buell, D.A., et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 7779 (2019), 505–510. https://doi.org/10.1038/s41586-019-1666-5
[2] Babai, L. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (2016), 684–697. https://doi.org/10.1145/2897518.2897542
[3] Bennett, C., Bernstein, E., Brassard, G., and Vazirani, U. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (1997), 1510–1523.
[4] Boppana, R., Håstad, J., and Zachos, S. Does co-NP have short interactive proofs? Information Processing Letters 25, 2 (1987), 127–132.
[5] Brown, T.B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D.M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Suskever, I., and Amodei, D. Language models are few-shot learners (2020). arXiv:2005.14165 [cs.CL]
[6] Bürgisser, P., Ikenmeyer, C., and Panova, G. No occurrence obstructions in geometric complexity theory. J. of the American Mathematical Society 32, 1 (2019), 163–193. https://doi.org/10.1090/jams/908
[7] Coldwell, W. World's longest pub crawl: Maths team plots route between 25,000 UK boozers. The Guardian (Oct. 21, 2016). https://www.theguardian.com/travel/2016/oct/21/worlds-longest-pub-crawlmaths-team-plots-route-between-every-pub-in-uk
[8] CRA Taulbee Survey. Computing Research Association (2020), https://cra.org/resources/taulbee-survey.
[9] Cook, B. Traveling salesman problem (2020), http://www.math.uwaterloo.ca/tsp/uk.
[10] Cook, S. The complexity of theorem-proving procedures. In Proceedings of the 3rd ACM Symposium on the Theory of Computing (1971), 151–158.
[11] Demaine, E.D. and Hearn, R.A. Playing games with algorithms: Algorithmic combinatorial game theory. Games of No Chance 3: Mathematical Sciences Research Institute Publications, Vol. 56. Michael H. Albert and Richard J. Nowakowski (Eds.), Cambridge University Press (2009), 3–56. http://erikdemaine.org/papers/AlgGameTheory_GONC3/
[12] Eykholt, K., Evtimov, I., Fernandes, E., Li, B., Rahmati, A., Xiao, C., Prakash, A., Kohno, T., and Song, D. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (2018).
[13] Fortnow, L. The status of the P versus NP problem. Commun. ACM 52, 9 (Sept. 2009), 78–86. https://doi.org/10.1145/1562164.1562186
[14] Fortnow, L. The Golden Ticket: P, NP and the Search for the Impossible. Princeton University Press, Princeton, (2013). https://goldenticket.fortnow.com
[15] Fortnow, L and Gasarch, W. Computational Complexity. https://blog.computationalcomplexity.org
[16] Garey, M. and Johnson, D. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, (1979).
[17] Gödel, K. Letter to John von Neumann. (1956). https://www2.karlin.mff.cuni.cz/~krajicek/goedel-letter.pdf
[18] Grover, L. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing (1996), 212–219.
[19] Hartnett, K. Building the mathematical library of the future. Quanta Magazine (Oct. 1, 2020). https://www.quantamagazine.org/building-the-mathematical-library-of-the-future-20201001/.
[20] Impagliazzo, R. A personal view of average-case complexity theory. In Proceedings of the 10th Annual Conference on Structure in Complexity Theory. IEEE Computer Society Press (1995), 134–147. https://doi.org/10.1109/SCT.1995.514853
[21] Jaffe, A. The Millennium Grand Challenge in Mathematics. Notices of the AMS 53, 6 (June/July 2006), 652–660. http://www.ams.org/notices/200606/feajaffe.pdf
[22] Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Tunyasuvunakool, K., Ronneberger, O., Bates, R., Žídek, A., Bridgland, A., Meyer, C., Kohl, S.A.A., Potapenko, A., Ballard, A.J., Cowie, A., Romera-Paredes B., Nikolov, S., Jain, R., Adler, J., Back, T., Petersen, S., Reiman, D., Steinegger, M., Pacholska, M., Silver, D., Vinyals, O., Senior, A.W., Kavukcuoglu, K., Kohli, P., and Hassabis, D. High accuracy protein structure prediction using deep learning. In 14th Critical Assessment of Techniques for Protein Structure Prediction (Abstract Book) (2020), 22–24. https://predictioncenter.org/casp14/doc/CASP14_Abstracts.pdf
[23] Karp, R. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher (Eds.). Plenum Press, New York, (1972), 85–103.
[24] Kearns, M. and Valiant, L. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM 41, 1 (Jan. 1994), 67–95. https://doi.org/10.1145/174644.174647
[25] Kirchherr, W., Li, M., and Vitányi, P. The miraculous universal distribution. The Mathematical Intelligencer 19, 4 (Sep. 1, 1997), 7–15. https://doi.org/10.1007/BF03024407
[26] LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Nature 521, 7553 (May 1, 2015), 436–444. https://doi.org/10.1038/nature14539
[27] Levin, L. Universal'ny̆ie pereborny̆ie zadachi (Universal search problems: in Russian). Problemy Peredachi Informatsii 9, 3 (1973), 265–266. Corrected English translation in.37
[28] McCulloch, W.S. and Pitts, W. A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics 5, 4 (Dec. 1, 1943), 115–133. https://doi.org/10.1007/BF02478259
[29] Murray, C. and Williams, R. Circuit lower bounds for nondeterministic quasi polytime: An easy witness Lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (2018), 890–901. https://doi.org/10.1145/3188745.3188910
[30] O'Neil, C. Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy. Crown (2016), New York.
[31] Peikert, C. Lattice cryptography for the Internet. In Post-Quantum Cryptography, Michele Mosca (Ed.). Springer International Publishing, Cham (2014), 197–219.
[32] Razborov, A. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR 41, 4 (1987), 333–338.
[33] Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Laurent Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, T., and Silver, D. Mastering Atari, go, chess and shogi by planning with a learned model. Nature 588, 7839 (Dec. 1, 2020), 604–609. https://doi.org/10.1038/s41586-020-03051-4.
[34] Shor, P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (1997), 1484–1509.
[35] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., and Hassabis, D. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362, 6419 (2018), 1140–1144. https://doi.org/10.1126/science.aar6404
[36] Smolensky, R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on the Theory of Computing (1987), 77–82.
[37] Trakhtenbrot, R. A survey of Russian approaches to Perebor (brute-force search) algorithms. Annals of the History of Computing 6, 4 (1984), 384–400.
[38]Wikipedia contributors. List of public corporations by market capitalization. Wikipedia, the Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=List_of_public_corporations_by_market_capitalization&oldid=1045945999.
[39] Williams, R. Nonuniform ACC circuit lower bounds. Journal of the ACM 61, 1, Article 2 (Jan. 2014). https://doi.org/10.1145/2559903.
本文经作者授权揭橥于《返朴》，原文译自Fortnow, Lance. "Fifty years of P vs. NP and the possibility of the impossible." Communications of the ACM 65.1 (2021): 76-85. DOI: 10.1145/3460351
特 别 提 示
1. 进入『返朴』微信"大众号底部菜单“佳构专栏“，可查阅不同主题系列科普文章。
2. 『返朴』供应按月检索文章功能。关注"大众年夜众号，回答四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。
版权解释：欢迎个人转发，任何形式的媒体或机构未经授权，不得转载和摘编。转载授权请在「返朴」微信公众年夜众号内联系后台。
