笔趣阁

手机浏览器扫描二维码访问

第679章 回到研究状态（第3页）

是多项式复杂程度的非确定性问题

简单的写法就是“NP=P？”

问题也就在这个问号上面

到底是NP等于P，还是NP不等于P

当然，几乎绝大多数的人，都希望NP等于P

因为这背后的实际意义，太过重大

只可惜，就算再多人的希望，也不能将这道千禧年大奖难题，给变成事实

它仍旧在等待着，能够解决它的人出现

“P类问题和NP类问题的关系……”

第一篇文献结束，陈舟看了看草稿纸上，自己所写的内容，小声的呢喃了一句

事实上，要知道“NP=P”是个什么问题，先要知道什么是P类问题，什么是NP类问题

P类问题和NP类问题这两个概念，是和计算理论中的时间复杂度有关的

至于计算理论中的时间复杂度，简单来说，就是解决一个问题的某种算法，所需要的计算量，随着这个问题的规模增长而增长的速度

这个概念，更多的被应用在信息学的计算机算法上

在算法中，时间复杂度本质上，是指计算量增长的速度，而不是这个算法运行的时间

自然的，对于同样的一个问题

如果采用不同的算法，其时间复杂度也是不一定相同的

而如果某个问题，能够找到的最优算法的时间复杂度，是n的多项式函数

那么，这个问题就被称之为P类问题

P也就是多项式的英文首字母

此外，还有一些问题，无论其是否能够在多项式时间复杂度内求解，如果知道一个随便给出的可能解，能够在多项式时间复杂度内验证其是否为所求的解

那么，这类问题就被称之为NP类问题

至于为什么要研究一个问题，是否有多项式时间复杂度的算法

则是因为，多项式时间复杂度的计算量增长速度，有些过于“快”了

随着n的增大，其计算量远远小于O（2^n）、O（n！）、O（n^n）这些时间复杂度问题

就好比那个很有名的大整数质因数分解问题

给出一个2048位的二进制整数，要找出它的某个质因数

一般来说，可能举全世界的计算能力，也需要上百年的时间，才能完成这个求解计算过程

但是，如果知道某一个质数的话

却可以用最普通的计算机，在几秒钟时间内，确定这个质数，是不是这个2048位二进制整数的一个因数

而这，便是不同时间复杂度，在实际计算过程中的差别！

虽说有时候快了不好，可是在时间复杂度上，还是快一点比较有应用价值

自然的，全部的P类问题，都属于NP类问题