有点烧脑

空调开好

超模君今天重温了综艺《百万富翁》，在想到底有没有一道题是价值百万的呢？

答案是有的，他就是著名的“千禧难题”。

千禧年大奖难题(Millennium Prize Problems),又称世界七大数学难题， 是七个由美国克雷数学研究所(Clay Mathematics Institute,CMI)于2000年5月24日公布的数学猜想。

这些都是极难的问题，其中大多数需要大量的专业知识，甚至光理解题目就很吃力了。

但只要你解破其中一题即可获奖金100万美元，相当于人民币6934900元。

为了照顾下学渣，今天要讲的是最容易理解和解释的一个。

☛ P=NP？

有捷径？没有捷径？

P=NP问题，其实就是在问生活是否存在大量可证明的捷径。

那么P和NP到底是什么？

P代表了这样一类问题，计算机在解决它们的时候可以有速度非常快的方法。这个速度和计算机硬件无关，仅仅取决于这个解决方法本身的便捷性。NP代表了另一类问题，它们有最优解，但是，其中很多问题，计算机在寻求最优解时，没有快速的方法，只能傻傻的、暴力的、尝试所有可能的组合，然后找到最优解。NP问题中，最难的一类问题，被称为NPC，也就是NP完全问题。

这个问题有什么意义吗？

意义就大大大了！

如果P=NP，则意味着，每一个NP问题都可以转化成P，也就是每一个难题最终可以变成一个简单命题，让计算机快速求解。

如果P≠NP，则意味着，很多NP问题无法简化成P，也就是计算机只能很傻很暴力的去求解。

跟我们这些普通的地球人有什么关系？

如果真的成立了，就意味着人类在解决复杂问题的时候就存在捷径了！

听起来好像很厉害的样子，能具体点吗？

假如P=NP的世界会怎样

试想下一个充满求解捷径的世界会是怎么样？

举一个场景，随着互联网的发展，RSA加密协议被广泛应用于各行各业，特别是电子商务。

RSA是什么？

RSA是目前最有影响力和最常用的公钥加密算法，基于计算乘积容易，分解因数则很难的数论事实，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。

就是这么一个目前安全系数最高的的协议，在P=NP的世界里将会被轻易破解。

RSA加密协议的核心——因数分解问题将变得能被高效地计算，我们可以找到几百万位数的质数因子。因此，P=NP将让RSA协议失效，所有基于公钥加密系统的协议也都将失效。

再来个栗子：蛋白质折叠问题也将会迎刃而解。当你需要进行癌症治疗时，不会是无法治愈的结果了。

科普一下，蛋白质会由所含氨基酸残基的亲水性、疏水性、带正电、带负电等特性通过残基间的相互作用而折叠成一立体的三级结构。

就是说蛋白质折叠涉及到内外部的不同因子的组合，导致其预测结构的可能性非常的多。因此，我们现阶段的难题就在于无法在短时间中从氨基酸序列计算出蛋白质结构，甚至无法得到准确的三维结构。

然而在P=NP的世界里，我们可以通过确切的程式算法，准确无误地制造出特定的蛋白质，其折叠方式不仅能有效地饿死癌细胞，而且对正常细胞没有任何影响。

另外，空当接龙、扫雷、数独等一些经典游戏也因为算法而在很大程度上变得索然无味。甚至说，当你在围棋对弈的时候，就已经知道正确的第一手，按照算法写好的剧本一直领先。

总之，在P=NP下，许多重要的未解之谜都可以被算法快速的KO了，特别是生物学和治疗癌症、商业和经济、破解网路金融的加密等等的难题。

最终有人可以证明吗？

但关于P和NP问题，目前还没有被证明。

但大多数人的观点是认为P≠NP。

因为当我们面临一个NP完全问题时，不可能找到一个在所有情况下都能解决该问题的算法。此时就要借助于其他方法，如近似计算、启发式方法、暴力破解等方法的组合，然后去尽可能的争取最好的结果。

然而证明P≠NP并非易事。你需要证明不存在有效的算法能解决团问题或任何其他的NP完全问题，这些算法除了包括现有的还包括将来发明的。

虽然如此，但就像费马大定理，从17世纪到1995年，历经三百多年的历史才被怀尔斯彻底证明。

同样，我们对解决这个问题仍然抱有希望。