我昨天无意中的吐槽有十万多盒友浏览，密码学真经不起惊吓，感觉大家对NP和P不是很了解，今天正好借着这个机会介绍一下。
在介绍之前，首先需要引入算法复杂度的定义，什么是算法复杂度，就是计算一个算法所需要的时间级别，也是衡量算法好坏的重要标准。
比如，我们我们设计一个相当简单的算法，竖式加法，如果两个数字都要n位，那么它们做加法就要做n次，算法复杂度就是O(N)。
如果是乘法，n位数乘m位数，需要做m*m次运算，复杂度就是O(MN)
即算法的执行时间可以用问题的规模表示，当问题复杂度公式不同时，运算时间差别很大。下图就是不同复杂度算法随问题规模扩大时运行时间的变化：
下面我们把复杂度分成两个大类，多项式级和指数级，多项式级就是说复杂度公式可以表示成n的多项式的模数，不管n的阶数多大，都算多项式级，比如O(N^100)，即n的一百次方，普遍观点认为，这个量级即使很巨大，但迟早会被穷尽，就像Intel的创始人摩尔提出的摩尔定律，集成电路上可容纳的元器件的数目，约每隔18-24个月便会增加一倍，性能也将提升一倍。所以多项式级都是可以接受的复杂度。
但是与之对应的是第二类，即指数级的，如O(2^N)，看上去好像比之前的O(N^100）小好多，但是事实上如果N足够大，指数增长的速度要远大于高阶多项式，且这个增长速度是不可接受的，算一辈子都算不完
明白了复杂度，接下来就可以引入 P 问题和 NP 问题，所谓的P 问题就是能够在多项式的时间复杂度内解决的问题，这里的 P 指的是多项式时间（polynomial time），对于那些不能在多项式的时间复杂度内解决的问题，比如说背包问题，分配问题等等，我们会认为这个问题很难，可能需要在指数或阶乘的时间复杂度内解决（之所以不把话说满是因为万一有人找到快速解法了呢），但是如果我们能够在多项式的时间复杂度内验证一个答案是否正确，我们就把这类问题称为 NP 问题，其中 NP 表示不确定的多项式时间（non-deterministic polynomial time）。简单来说就是解决 NP 问题很难，但验证它却很容易。打个比方，数独是一个解决起来比较难的问题，但是如果我们往格子里随机填一些数字，然后验证它是否满足数独的规则就会比较容易。因此，这类问题也是科学家们最关心的问题。
为了分析NP问题，有人发明了规约，所谓规约，就是问题A不会比问题B更难，那么B可以规约到A，如果解决了B，那么A也可以被解决。
那么问题来了，规约过后的 NP 问题能否在多项式的复杂度内解决呢？换句话说，P 问题和 NP 问题是否等价。如果 P = NP ，就意味着任何能够在多项式的复杂度验证的问题也能够在多项式的复杂度解决它！
它的意义何在呢？意义肯定是具有两面性。
首先是好处：由于很多 NP 问题难以在多项式复杂度内解决，而若 P = NP，就意味着可以把 NP 问题转换为 P 问题，这样一来，很多当前觉得困难的问题就能轻易被解决。比如在围棋方面会有终极解法，生物领域能轻松破解遗传密码并随意操纵基因序列，很多数学猜想也可以借助计算机进行演算推导，许多难题都能迎刃而解。
但随之而来也有坏处：由于所有公钥密码学都基于NP不等于P的假设，所有公钥加密和签名认证算法会彻底失效，你的银行卡，社交账号变得不再安全，黑客能够轻松进入你的电脑，我们都将没有秘密可言；比特币，区块链这些基于密码学的大热领域将完全崩塌，你可以轻松挖几百万个比特币，不过到时候它们将毫无价值。
最严重的是，我毕业就要失业（密码学专业学生太惨了）
不过话说回来，目前学界大部分都倾向于NP不等于P，且这个千禧年七大难题之一没那么容易被证明，至于文章开头那个宣称证明NP=P的天才少年？如果他的证明是对的，中科院院长都得他来当。
参考：
一文理解NP完全理论，NP问题，NPC问题-腾讯云开发者社区-腾讯云 (tencent.com)
P问题、NP问题、NP完全问题和NP难问题 - 知乎 (zhihu.com)
怎么理解 P 问题和 NP 问题？ - 知乎 (zhihu.com)