科学网—漫谈P vs NP问题
精选
已有 6250 次阅读
2024-7-5 07:39
| 个人分类: STEM札记 | 系统分类: 海外观察
“ 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 2 （ n ）） - 对数时间 ； O （ n ） - 线性时间 ； O （ n k ） - 多项式时间 ； O （ k n ） - 指数时间 ； O （ n ！） - 阶乘时间 等等。 其中 k 是常数， n 是输入大小。 n 的大小还取决于问题定义。例如，使用大小为 n 的数字集，搜索问题的平均复杂度介于线性时间和对数时间之间，具体取决于所使用的数据结构。
一个包含 n 和 n k 的数学表达式叫做多项式，这就是 “ P = NP ” 中的 “ P ” 所代表的意思。 P 是一组问题，其求解时间与涉及 n 的多项式成正比。显然，执行时间与 n 2 成比例的算法比执行时间与 n 成比例的算法要慢。但是， 与 多项式时间 和 指数时间 之间的区别相比，这种差异变得微不足道 。 例如， 如果一个执行时间与 n 成正比的算法 （ 线性时间 ） ，执行一次涉及 100 个元素的计算需要 1 秒，那么一个执行时间与 n 3 成正比的算法 （ 多项式时间 ） ， 大约 需要 2.8 小时。但是 ， 一个执行时间与 2 n 成正比的算法 （ 指数时间 ） 则 需要 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-H ard 关系
所以 ， 问题 “ 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
转载本文请联系原作者获取授权，同时请注明本文来自王宏琳科学网博客。 链接地址： https://blog.sciencenet.cn/blog-3005681-1440985.html
上一篇： 漫谈波 下一篇： 漫谈美国顶尖的大学的校训和吉祥物