理解 P/NP 问题时,我产生了一种已经触碰到人类认知天花板的错觉?!

本文涉及的产品
密钥管理服务KMS,1000个密钥,100个凭据,1个月
简介: 咱研究算法的时候,一定遇到过动态规划中的 旅行商问题(TSP)!TSP 是一个 NP 完全问题,今天咱要聊聊正是七大 千禧年大奖难题 之首的 【P/NP 问题】!

image.png

概念初识



咱研究算法的时候,一定遇到过动态规划中的 旅行商问题(TSP)

TSP 是一个 NP 完全问题,今天咱要聊聊正是七大 千禧年大奖难题 之首的 【P/NP 问题】!


  • 注:每解破一道千禧年大奖难题可获奖金100万美元


其实,本瓜在前不久的一篇文章《做题家:不可不会的“算法设计与分析”!》中提过一嘴:

“了解 P/NP 问题!有一种让我觉得已经触碰到人类【数学天花板】的错觉。😵”


现在再看这句话,我小了,格局小了! 此句应更正为:

“P/NP 问题应该是现代人类【认知的天花板】!它有着足以颠覆整个世界的力量!💪”


那究竟什么是 P/NP 问题 ???


一言以蔽之:

如果一个问题的解,可以在多项式时间内被验证(P),那么是否证明可以在多项式时间内找到这个解(NP)?

  • 多项式时间:如 O(n2)、O(n100)、O(n200) 等;如果能证明是可以的(即 P = NP),或者证明是不可以的(即 P ≠ NP),您就能拿 100 万美金了。


最通俗来讲,如果证明了 P = NP,就意味着:【当我们提出一个问题的验证方法后,我们就能获得了这个问题的解!】


这是非常恐怖的一句话!当代计算机科学和信息技术的基础是 P ≠ NP,如果证明了 P = NP,世界将迎来大变革!

  • 2002 年对 P/NP 领域专家的一次调查显示,相信 P = NP 以及 P ≠ NP 的专家的比例是 9:61。

举个栗子



举个例子🌰:

数独问题,验证很容易,只要遍历行和列去检查就可以了,时间复杂度是 O(n2)。

但是,反过来,如果给你一个数独问题,你是否能在多项式时间内求出它的解?

image.png


目前的结论是:不确定!


再举一例🌰:

当我告诉 319 是两个质数的乘积时(即告诉了验证方法),请问 319 是哪两个质数的乘积呢?如果是一个非常非常大的质数呢?


这个问题,和数独问题一样,能在多项式时间内验证(做乘法运算即可),但不确定是否能在多项式时间内求解。

即它们的特点:很好验证,但是求解很难!!

现实中还有非常多的这类例子🌰:

我们可以在多项式时间内验证它(P:polynomial time),但是不确定否可以在多项式时间内找到这个解(NP:nondeterministic polynomial time)。


比如:资源调度问题、图着色问题、哈密顿回路问题、旅行商问题......

比特币卒



如果 P = NP,现代【非对称加密】的密码体系会彻底崩掉(比如比特币等加密货币,会直接消失)。

我们知道非对称加密体系:通过私钥可以算出公钥,而通过公钥无法算出私钥。


image.png


这种非对称性是安全的最强重要保障!

私钥(K)* G = 公钥(P)
公钥(P)/ G = 私钥(K)


对私钥(K)做 G 运算,得出 公钥(P),这个很容易!(验证容易

但是由公钥(P)做 G 运算的逆运算得到 私钥(K),目前认为是:非常非常非常难的,几乎不可能,这是加密安全的最重要基础!(求解困难)。


如果证明了 P = NP,那么我们就可以通过计算机在多项式时间内算出这个私钥解啦!那就没有加密可言啦!!所以,加密体系也就崩溃掉了!!

你可能会疑问:这个多项时间如果很大呢,比如 O(n100)?


答:只要 P = NP,即使这个多项式时间很大,我们迟早也能把它算出来!因为问题不变,算力是不断提升的。量子计算

这样说,如果现代密码系统崩溃,其中的利益远远大于破解 P/NP 问题的 100 万美元~


人与机器



更加细思极恐的是,如果证明了 P = NP,【人与机器】的界限开始变得模糊。

MIT 计算机科学和人工智能实验室教授 Scott Aaronson 说:

“如果 P = NP 的话,这个世界将是完全不同的地方。任何创意都不再会有价值!一个问题被找到后,从认知它到解决它不会再有遥不可及的距离。喜欢交响乐的人,可以成为莫扎特;喜欢逐步论证的人,可以成为高斯。艺术和智能都由计算的深层架构所模制。”


意味着:无论多复杂的问题,只要能在多项式时间内验证,就代表着我们能在多项式时间内解决它。即使是艺术创造!

计算机能精确地模仿某一个特定的人。网络的身份鉴定将变得相当困难,以致于不得不借助物理方式;


万物归一



肖邦曾说过:

“简单是最终的成就。”


我们将 P/NP 问题的释义再夸张一点:

P/NP 终极之问:世界上一切复杂的问题是不是都能变成简单的问题?

没人知道。


或许人类最终无法找到这最简单的真理,就像游戏里的人物无法理解我们一样。

这个宇宙是混沌的?还是有序的?

呜呼~这次算是顶到天花板了QAQ?一切归于寂寥......


推荐阅读




相关文章
|
决策智能
博弈论第十一集总结(进化稳定—合作,突变,与平衡 “ 观后感)
博弈论第十一集总结(进化稳定—合作,突变,与平衡 “ 观后感)
74 0
|
定位技术 图形学
窥探他人眼中的世界:用眼睛反光重建3D场景,《黑镜》走进现实
窥探他人眼中的世界:用眼睛反光重建3D场景,《黑镜》走进现实
145 0
|
人工智能 边缘计算 搜索推荐
就餐这件小事,如何被AI计算深度改变?
天天嚷着营养均衡、保持身材,临了却不知道该吃什么、怎么吃;
就餐这件小事,如何被AI计算深度改变?
珍爱生命,远离大论战
  前几天小学聚会,想起来了一些小时候的趣事。有一同学,他学习能力强,学东西快,老师讲的课程他都会了,作业也都写完了。然后呢呆着没事,找他同桌闲聊,放学了还拉着他疯玩。结果呢,第二天要交作业,他是没事了,可是他同桌惨了,忘记写作业了。
932 0
|
机器学习/深度学习 人工智能 算法
顾险峰:技术爆炸的亲历观察
数百年后,如果人类依然没有被人工智能所毁灭,在撰写现代历史的时候,可能最为恰切的概括就是“技术爆炸”。
2294 0