【数学】做对就给100万，颠覆计算机的P对NP问题

粉丝福利 

严伯钧的硬派科普秀交流群来啦，跟着严老师一起聊聊科普、了解物理界新动向、第一时间get严老师的活动消息，还有不定期的社群活动福利哦。

入群方式
微信添加yan_bojun，并回复：科普秀，我们将会邀请你入群。

欢迎每一位在听《严伯钧的硬派科普秀》的你的到来。

精华笔记 

P对NP问题可以说是计算机算法理论中最重要的问题。

一、复杂度
1. 计算机在进行运算时，针对同一个问题可以有不同的算法，每一个算法都有一个表示它优秀与否的量，叫复杂度；

2. 随着样本数的增大，不同算法的复杂度有不同的变化规律。有些算法的复杂度呈线性增长，也有些呈对数、指数增长；

3. 算法中有一个重要的研究方向就是如何降低复杂度，可以说是算法的算法；

二、P对NP问题
4. P对NP问题，是复杂度研究里的一个重要方向。P问题就是拥有多项式算法的判定问题。即某个问题算法的复杂度，可以写成其规模n的多项式，比如n的平方或三次方。简单的加减乘除都是P问题；

5. 由于计算机进行一次计算的时间是固定的，所以复杂度就正比于解决问题的时间；

6. 相比之下，NP问题更加复杂。此类问题虽然验证起来很容易，复杂度同样可以是n的多项式，但是解的复杂度就更高，比如数独；

三、如果“P=NP”会怎样？
7. P对NP问题，就是问P问题和NP问题本质上是不是一样的？或者说NP问题是不是其实也有P问题形式的算法。因为对于计算机来说，没有难度高低的区别，只有复杂度的大小。所谓的难与不难，只是人类思维逻辑的局限。比如费马大定理，虽然找到解决方案的思维方式很难，但是解决问题所用的步骤并不多；

8. 如果“P=NP”的话，就意味着在原理上，所有的NP问题都是P问题，那将是对计算机技术的革命。比如，我们现在认为密码是人为设计的NP问题，破解起来复杂度极高。但是如果“P=NP”成立的话，破解密码就变得不再困难了；

9. P对NP问题是70年代提出的，目前学术界有两派观点，大多数学者认为P≠NP。2010年有一个HP的工程师号称解出了P对NP问题，虽然后来被指出有很多不足，但他的尝试为学界提供了新的思路和方向。