理解 P\u002FNP 问题时，我产生了一种已经触碰到人类认知天花板的错觉？！
理解 P\u002FNP 问题时，我产生了一种已经触碰到人类认知天花板的错觉？！
theme: awesome-green
「本文已参与好文召集令活动，点击查看：后端、大前端双赛道投稿，2万元奖池等你挑战！」
概念初识
咱研究算法的时候，一定遇到过动态规划中的 **旅行商问题（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问题为什么这么难？
- 科學家發現人類的意識與宇宙的混沌本質有關
我是掘金安东尼，输出暴露输入，技术洞见生活，下次再会~