我昨天无意中的吐槽有十万多盒友浏览，密码学真经不起惊吓，感觉大家对NP和P不是很了解，今天正好借着这个机会介绍一下。
在介绍之前，首先需要引入算法复杂度的定义，什么是算法复杂度，就是计算一个算法所需要的时间级别，也是衡量算法好坏的重要标准。
比如，我们我们设计一个相当简单的算法，竖式加法，如果两个数字都要n位，那么它们做加法就要做n次，算法复杂度就是O(N)。
但是与之对应的是第二类，即指数级的，如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)
#免责声明#
①本站部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责。
②若您需要商业运营或用于其他商业活动，请您购买正版授权并合法使用。
③如果本站有侵犯、不妥之处的资源，请联系我们。将会第一时间解决！
④本站部分内容均由互联网收集整理，仅供大家参考、学习，不存在任何商业目的与商业用途。
⑤本站提供的所有资源仅供参考学习使用，版权归原著所有，禁止下载本站资源参与任何商业和非法行为，请于24小时之内删除!
