可能改变世界的数学问题:p = np吗?

2000年,克莱数学学院提出了七个未解决的数学问题,并向任何可以解决这些问题的人提供了100万美元。到目前为止,只有七个所谓的千年proble中的一个

2000年,克莱数学学院提出了七个未解决的数学问题,并向任何可以解决这些问题的人提供了100万美元。到目前为止,已经解决了七个所谓的千年问题中的一个:庞加莱的猜想,这与如何在不同的空间维度定义球体有关。

对于非数学家的人来说,这个问题的性质又是为什么价值100万美元的人都很难缠绕自己的头。但是,另一个千年问题更容易理解,解决它将对我们的世界运作方式产生巨大后果。尽管看似更直接,但绝对地以一种或另一种方式证明了这个问题已有数十年了。问题是p = np。

快门

什么是P和NP问题?

简而言之,P与NP问题询问是否可以轻松解决的问题集是否也可以轻松检查。想象一下,您的任务是将破碎的茶杯重新粘合在一起。很容易看出您是否成功了 – 您将在面前有一个完整的茶杯。但是,很难将所有不同的碎片放回原处。这是NP问题的一个例子;难以解决,易于检查。

现在,想象一下,您的任务是计算茶杯破裂的碎片,而不必重新组装。这将是一个问题。计数破碎的碎片比弄清楚它们如何相互连接要容易得多。

为什么这两个问题集称为P和NP?

计算机算法需要一定时间来解决他们的任务问题。通常,您可以大致估计使用需要处理的元素数量将花费多少时间。计算机科学家称元素的数量为n。因为某些算法比其他算法效率更高,因此他们完成的时间可能与N,N2,N3等有关。不过,重要的是指数是常数 – 它的1或2等。在这种情况下,据说算法在多项式时间或P中完成。

不幸的是,并非所有问题都可以使用。解决某些问题可能会使算法与2N,3N等成正比的时间量。在这种情况下,n是指数,这意味着该算法必须处理的每个元素都会呈指数增长。在这种情况下,算法可以在指数时间或NP(实际上代表非确定的多项式时间)完成。

这两个之间的区别可能很大。如果P算法具有100个元素,并且其完成工作的时间与N3成正比,那么它将在大约3小时内解决其问题。但是,如果它是NP算法,并且其完成时间与2N成正比,那么大约需要300亿年来。

Flickr用户JanKaláb

为什么这很重要?

询问p = np是否是询问每个困难问题是否真正包含一个简单但隐藏的解决方案的另一种方法。这两个问题的味道是否不可撤销地分开?他们的基本性质简单地复杂吗?

如果P确实相等,那么它将对我们的生活方式产生一些重大影响。一个主要的好处是,许多NP问题被称为NP完整问题,这意味着他们的解决方案可以迅速适应任何其他NP完整问题。因此,开发一种快速解决一个NP完整问题的方法将在完成所有其他NP完整问题方面取得了长足的进步。哪些NP问题的示例是什么?许多研究人员专注于一个主要问题。大多数现代密码学依赖于难以破解但易于检查的代码。例如,考虑到您的各个帐户的密码或引脚。检查它们是正确的,但是蛮力猜测字母和数字的每一个置换都将永远消失。在亚马逊上订购某些东西时,确保信用卡号的加密是NP密码学的一个例子。如果p = np,那么破裂几乎每种加密都会突然变得更加容易。

虽然失去任何互联网安全性会造成灾难性,但如果p = np,将会产生许多有益的后果。兰斯·福特诺(Lance Fortnow)是计算机科学家,也是金票的作者:P,NP和寻找不可能的人,总结了ACM通信的文章中的一些主要后果:

所有表格的运输将最佳地安排,以使人们和商品更快,更便宜。制造商可以改善生产以提高速度并减少浪费。而且我只是在刮擦表面。通过使用Occam剃须刀的原理,学习变得容易 – 我们只是找到与数据一致的最小程序。几乎完美的视力识别,语言理解和翻译以及所有其他学习任务变得微不足道。我们还将对天气和地震以及其他自然现象有更好的预测。这个问题是P = NP是否如此基础,以至于很难仅选择少数可以通过光年来改进的代表任务。例如,从其氨基酸序列中预测蛋白质结构是相对容易的,这是设计药物和生物技术的重要里程碑。另一个普遍引用的NP问题是如何确定计算机芯片上最有效的晶体管布局,从而显着增强了计算能力。

实际上,证明p = np将使几乎所有其他数学问题更容易,更容易。 Fortnow还写道:“一个证明P = NP的人将从克莱研究所(Clay Institute)回家,而不是100万美元的支票,而是有七个(实际上是六个,因为庞加莱的猜想似乎已经解决了)。”

最终,证明p = np的后果将是当前社会技术和经济基础的全部颠覆。很可能,解决这个问题将是对互联网的发明的创新性提升。

科学共识

不幸的是,大多数计算机科学家都不认为P = NP(与2012年一样,有83%的计算机科学家认为这一主张是真实的。很难证明是负面的,但是所有失败的尝试都证明了p = np对两种类型的问题最终是不可调和的想法。麻省理工学院的科学家斯科特·阿隆森(Scott Aronson)撰写了一篇博客文章,列出了p最有可能不等于NP的十个原因,而第九号的论点却明显地消除了p = np的想法,即p = np和简洁地描述了后果,如果p = np = np。 ,那么世界将是一个与我们通常假设的地方完全不同的地方。 “创造性飞跃”没有特殊的价值,解决问题和确认解决方案之间没有根本的差距。每个能欣赏交响曲的人都是莫扎特。每个可以逐步论证的人都是高斯。沃伦·巴菲特(Warren Buffett)都会认识到一个良好的投资策略的每个人。

一旦知道最好的学习,任何人都可以成为数学人……

content.jwplatform.com

任何人都可以成为数学人 – 一旦他们理解这一点。

原创文章,作者:新鲜事,如若转载,请注明出处:http://www.dsonekey.com/3414.html

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息