概念初识
咱研究算法的时候,一定遇到过动态规划中的 旅行商问题(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)。
但是,反过来,如果给你一个数独问题,你是否能在多项式时间内求出它的解?
目前的结论是:不确定!
再举一例🌰:
当我告诉 319 是两个质数的乘积时(即告诉了验证方法),请问 319 是哪两个质数的乘积呢?如果是一个非常非常大的质数呢?
这个问题,和数独问题一样,能在多项式时间内验证(做乘法运算即可),但不确定是否能在多项式时间内求解。
即它们的特点:很好验证,但是求解很难!!
现实中还有非常多的这类例子🌰:
我们可以在多项式时间内验证它(P:polynomial time),但是不确定否可以在多项式时间内找到这个解(NP:nondeterministic polynomial time)。
比如:资源调度问题、图着色问题、哈密顿回路问题、旅行商问题......
- wiki:List of NP-complete problems这些看似是数学问题、信息技术问题,但是却体现在生活的方方面面!
比特币卒
如果 P = NP,现代【非对称加密】的密码体系会彻底崩掉(比如比特币等加密货币,会直接消失)。
我们知道非对称加密体系:通过私钥可以算出公钥,而通过公钥无法算出私钥。
这种非对称性是安全的最强重要保障!
私钥(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?一切归于寂寥......
推荐阅读
- 浅谈P vs. NP
- 椭圆曲线加密与哈希函数是什么?非对称加密是什么?比特币中的数学原理
- 世界七個數學難題之一:P與NP @Hackerdashery
- NP难问题求解综述
- P 不等于 NP……么?
- 假如P=NP,世界将会怎样?
- 最新证明面临质疑:P/NP问题为什么这么难?
- 科學家發現人類的意識與宇宙的混沌本質有關