理解 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?一切归于寂寥......


推荐阅读




相关文章
|
机器学习/深度学习 编解码 人工智能
被低估且误解的换脸技术: 揭秘换脸技术本身的领域及行业价值
本文主要用尽量简单白话的描述来剖析下AI换脸技术的原理,做一个科普文章,了解下当前换脸技术的发展现状及其局限性。
|
决策智能
博弈论第十一集总结(进化稳定—合作,突变,与平衡 “ 观后感)
博弈论第十一集总结(进化稳定—合作,突变,与平衡 “ 观后感)
73 0
|
定位技术 图形学
窥探他人眼中的世界:用眼睛反光重建3D场景,《黑镜》走进现实
窥探他人眼中的世界:用眼睛反光重建3D场景,《黑镜》走进现实
143 0
|
人工智能 边缘计算 搜索推荐
就餐这件小事,如何被AI计算深度改变?
天天嚷着营养均衡、保持身材,临了却不知道该吃什么、怎么吃;
就餐这件小事,如何被AI计算深度改变?
|
大数据 智能硬件
丁道师:电影“票补”降温反映市场正回归理性
丁道师:电影“票补”降温反映市场正回归理性
130 0
|
人工智能
ANN让外星人无处可藏?人工智能预测其他行星上的生命迹象
英国普利茅斯大学(Plymouth University)的最新研究发现,人工智能可以帮助天文学家寻找外星生命。该学校的科学家正在通过人工神经网络(ANNs)来预测其他行星上存在生命的可能性,进而为未来星际空间任务寻找有望实现的目标。
1738 0
|
机器学习/深度学习 人工智能 算法
顾险峰:技术爆炸的亲历观察
数百年后,如果人类依然没有被人工智能所毁灭,在撰写现代历史的时候,可能最为恰切的概括就是“技术爆炸”。
2293 0