spring63的个人博客分享 http://blog.sciencenet.cn/u/spring63

博文

漫谈P vs NP问题 精选

已有 4409 次阅读 2024-7-5 07:39 |个人分类:STEM札记|系统分类:海外观察

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

1  PNP

       19715科学家/数学家史蒂夫·库克(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记号。例如,Olog2n)) - 对数时间On- 线性时间Onk- 多项式时间Okn- 指数时间On!) - 阶乘时间等等。其中 k 是常数,n 是输入大小。n 的大小还取决于问题定义。例如,使用大小为 n 的数字集,搜索问题的平均复杂度介于线性时间和对数时间之间,具体取决于所使用的数据结构。

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

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

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

2  复杂度类

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

只有P型和NP型问题吗?答案是否定的。除了P和NP,还有NP-HardNP-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左)

image.png 

1 PNPNP-CNP-Hard关系

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

3  研究动态

正如我们前面提到的,P可能不等于NP既然可能永远找不到NP问题的有效解决方案为什么人们仍然关注P vs NP”问题呢?实际上,PNP问题的研究,对于加深我们对计算复杂性的理解非常重要。佐治亚理工学院研究PNP问题的计算机科学家理查德·利普顿说,试图回答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])。

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

参考资料:

[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

上一篇:漫谈波
下一篇:漫谈美国顶尖的大学的校训和吉祥物
收藏 IP: 219.142.27.*| 热度|

4 郑永军 王涛 张林 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (3 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-7-20 14:18

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部