“P vs NP”是计算机科学中最著名的未解决的难题之一，困扰了理论计算机科学家50多年。程序员和计算机科学家一直在讨论解决计算机科学中这个棘手的问题。克雷数学研究所（Clay Mathematics Institute）将其列为“千禧年”问题之一，并承诺向首个证明或推翻该难题的人提供100万美元的奖赏。

1  P与NP

       1971年5月，科学家/数学家史蒂夫·库克（Steve Cook）在他的论文《定理证明程序的复杂性》（The Complexity of Theorem Prove Procedures）中，向世界介绍了P vs NP问题。50多年过去了，世界仍在努力解决它。

如果检查问题的解决方案是否正确很容易，那么解决问题是否也很容易？这就是P vs NP问题的本质。NP问题的典型例子是哈密顿路径问题：给定一个有n个城市的地图网络，寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。如果你给我一个解决方案，我可以轻松检查它是否正确。但找到解决方案并不容易。

  粗略地说，“P”级问题是对计算机来说是“容易”解决的；也就是说，与问题的复杂性相比，可以在合理的时间内计算出这些问题的解决方案。而对于“NP”问题，解决方案可能很难找到——甚至于需要数十亿年的计算——但一旦找到，就很容易验证。“P vs  NP”不仅仅是一个抽象的数学难题。它试图一劳永逸地确定哪些类型的问题可以由计算机解决，哪些类型的问题不能解决。NP类问题包括许多具有重大实际意义的模式匹配和优化问题，如确定硅片上晶体管的最佳排列、开发精确的金融预测模型，或分析细胞中蛋白质的折叠行为。

  “P=NP？”问题问的是这两个类是否实际上是相同的——即，是否每个NP问题也是P问题。如果P等于NP，那么每一个NP问题都包含一个隐藏的快捷方式，允许计算机快速找到完美的解决方案。但是如果P不等于NP，那么就不存在这样的捷径，计算机解决问题的能力将永远受到根本性的限制。

   到目前为止，主流答案是P不等于NP。这虽然被学术界已经大多数人所接受，但这个问题本身仍然属于悬而未决的问题。事实上，早在2002年的一项民意调查中，61名数学家和计算机科学家认为P可能不等于NP，只有9人认为P等于NP，而在这9人中，有几位告诉民意调查员，他们采取的立场只是为了逆反。但到目前为止，还没有人能够以一种或另一种方式果断地回答这个问题。MIT计算机科学和人工智能实验室的复杂性研究员斯科特·阿伦森说（Scott Aaronson）说。“很少有人相信P等于NP，这是有充分理由的，”他说。“如果相等，我们将生活在一个完全不同的宇宙中…”

计算机科学关注的主要问题之一是：需要多长时间执行一个给定的算法。但计算机科学家不会以分钟或毫秒给出答案；他们根据算法需要处理的元素数量来给出——计算机科学家指定n。他们常用大-O记号。例如，O（log₂（n）） - 对数时间；O（n）- 线性时间；O（n^k）- 多项式时间；O（kⁿ）- 指数时间；O（n！） - 阶乘时间等等。其中 k 是常数，n 是输入大小。n 的大小还取决于问题定义。例如，使用大小为 n 的数字集，搜索问题的平均复杂度介于线性时间和对数时间之间，具体取决于所使用的数据结构。

一个包含n和n^k的数学表达式叫做多项式，这就是“P = NP”中的“P”所代表的意思。P是一组问题，其求解时间与涉及n的多项式成正比。显然，执行时间与n²成比例的算法比执行时间与n成比例的算法要慢。但是，与多项式时间和指数时间之间的区别相比，这种差异变得微不足道。例如，如果一个执行时间与n成正比的算法（线性时间），执行一次涉及100个元素的计算需要1秒，那么一个执行时间与n³成正比的算法（多项式时间），大约需要2.8小时。但是，一个执行时间与2ⁿ成正比的算法（指数时间）则需要4万亿亿年。n越大，差异越大。

NP是其解可以在多项式时间内验证的问题集。用计算理论的术语说，NP（非确定性多项式时间）问题，是一类计算问题，可以由非确定性机器在多项式时间内求解，并且可以通过确定性机器在多项式时间内验证。这里，“确定性机器”是指在特定输入条件下产生相同输出的机器。这种机器的行为是事先确定的，不受随机性或不确定性的影响。“非确定性机器”是一种计算机模型，其中在给定输入的情况下可能有多种可能的执行路径。机器不按照固定的规则顺序执行指令，而是根据某些条件进行选择。它与确定性机器的不同在于：确定性机器的每一步只能转移到一个状态，而非确定型机器可以“同时”转移到多个状态，从而在多个“分支”并行计算。这种机器在计算理论和算法设计中起着重要作用。

众所周知，NP问题中的许多都需要指数级的时间来解决。例如，我们无法有效地分解巨大的合数（一个经典的NP问题）构成了现代密码学的基础——它支撑着从国家安全到电子商务的一切。NP中最著名的指数时间问题，可能是寻找一个大数的质因数。验证一个解决方案只需要乘法，但是解决这个问题需要系统地尝试许多候选方案。

2  复杂度类

现在，在理论计算机科学中，常见问题定义的分类和复杂度有两大集合：P是“多项式”时间，NP是“非确定性多项式”时间。P通常是一类可解决和可处理的问题，示例：计算最大公约数、哈希表找找、排序问题。NP类解决方案难找，但NP问题的解容易验证。示例：整数分解、可满足性（SAT）。

只有P型和NP型问题吗？答案是否定的。除了P和NP，还有NP-Hard和NP-C，我们用它来表达更复杂的问题。

NP-Hard是一类问题，是指NP中所有问题都能够在多项式时间复杂度归约到的问题。NP-Hard不必属于NP（不在NP中的NP-Hard问题验证时间可能很长）。示例有：停机问题、旅行推销员问题。所有最优化问题属于NP-Hard问题。

NP-C（即，NP-Complete）问题是NP问题的子集，是NP和NP-Hard交集。NP-C问题是NP集中最难的问题。如果NP-C中的任何一个问题可以在多项式时间内求解，那么NP中的每个问题都可以在多项式时间内求解。示例有：确定图是否有哈密顿回路、确定布尔公式是否满足。决策问题属于NPC。

如果P不等于NP，在从易到难的评级中，我们可能会将它们自下而上标记为“简单”、“中等”、“困难”，最后是“最难”（图1左）。

图1 P、NP、NP-C和NP-Hard关系

   所以，问题“P等于NP吗？”意思是“如果一个问题的解可以在多项式时间内被验证，那么，它是否可以在多项式时间内被找到？”NP问题研究非常重要的原因之一是现代加密技术依赖于P不等于NP这一事实。如果P等于NP，那么素数分解可以由计算机在多项式时间内解决，这实际上会泄露数据的密钥，因为素数分解是产生密钥的基础。

3  研究动态

正如我们前面提到的，P很可能不等于NP。既然可能永远找不到NP问题的有效解决方案，为什么人们仍然关注“P vs NP”问题呢？实际上，P与NP问题的研究，对于加深我们对计算复杂性的理解非常重要。佐治亚理工学院研究P与NP问题的计算机科学家理查德·利普顿说，“试图回答‘P不等于NP’的假设，有助于我们开发新的思维技术”。例如，由麻省理工学院发明的RSA加密方案，通常用于安全的互联网交易，实际上是对进行某些数论计算的复杂性研究的结果。又如，彼得·肖尔（Peter Shor）发现了一种在量子计算机上因数分解的方法。肖尔的发现激发了人们的希望，即量子计算机可以在多项式时间内解决NP-C问题。因式分解问题实际上是为数不多的已知NP-C问题之一。

50年来，计算机科学家一直试图解决“P vs NP”问题。计算机科学家思考一个元问题: 证明P = NP有多复杂？本·布鲁贝克（Ben Brubaker）探索了元复杂性（meta-complexity）问题。元复杂性是指计算和任务的复杂性——评估问题的复杂性。2023年春天加州大学伯克利分校的西蒙斯研究所举办了关于这个主题的研究项目（参考资料[1]）。从事元复杂性研究的计算机科学家不仅展示了各种复杂性度量之间的联系，还发现了他们自己的子领域与计算机科学其他领域之间的深层联系，如学习理论和密码学。元复杂性的研究范围在过去10年里急剧扩大，因为突破表明，密码原语和学习原语，最终不仅可以简化为元计算问题的解决方案，而且相当于元计算问题的解决方案。

我们生活在一个人工智能被应用于许多不同情境的时代。有研究者正在利用人工智能的新方法，从信息论的角度重新构思P  vs NP问题，探索机器学习如何与P vs NP相啮合（参考资料[2]）。

顺便说，在写这篇博客时候，2024年7月2日，有海外媒体报道，在人工智能工具的帮助下，困扰数学家40多年的“忙碌海狸”难题取得突破性进展。忙碌的海狸（The Busy Beaver Problem）问题，是一个有趣的理论计算机科学问题：给定一个具有两个符号字母 {0，1} 的n状态图灵机，机器在停止之前可以在初始空白磁带（填充0）上打印1的最大数目是多少？探索繁忙的海狸函数BB（n）吸引了一代又一代的计算机科学家、数学家和业余爱好者。对于较小的状态，早已经有了答案：BB(1) = 1；BB(2) = 6；BB(3) = 21；BB(4) = 107。现在，通过广泛合作的研究项目证明了：BB(5) = 47,176,870，并使用Coq辅助证明软件将证明翻译为经过正式验证的逻辑，提供最高标准的严谨性。据报道，下一步，将探索BB(6)。但是，也有报道称，BB（6）可能有难以逾越的障碍，那么，BB（5）就是我们能够知道的最后一个的忙碌海狸数字。

参考资料：

[1] Adam Becker. Meta-Complexity: A Basic Introduction for the Meta-Perplexed. FEB. 28, 2024

https://simons.berkeley.edu/news/meta-complexity-basic-introduction-meta-perplexed

[2] Andrea Berdondini. AI Solves The P Versus NP Problem. January 24, 2024

https://towardsai.net/p/machine-learning/ai-solves-the-p-versus-np-problem