第679章 回到研究状态(3 / 4)

随着n的增大,其计算量远远小于O(2n)、O(n!)、O(nn)这些时间复杂度问题。

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

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

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

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

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

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

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

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

看着草稿纸上的内容,陈舟已经给出了这一显而易见的解释。

一个问题可以在多项式时间复杂度内求解,当然可以在多项式时间复杂度内验证。

只不过,写完这行文字的陈舟,又在下面加了一个“?”。

问号的旁边,陈舟写到:“反过来呢?”

没错,反过来呢?

一个可以在多项式时间复杂度内验证的问题,又是否能够通过多项式时间复杂度的算法求解呢?

陈舟暂时不知道。

所以,他在这个反问的话下面,划上了两道横线。

实际上,这个反问的话,其实也就是,是否全部的NP类问题,都属于P类问题呢?

而这,便是著名的NP完全问题,也就是“NPP?”。

陈舟虽然还不知道这个问题的答案。

但是,已经不是信息学小白的陈舟,自然知道这个问题的答案,所具有的现实意义。

如果“NPP?”没有了问号。

也就意味着,任何一个原来找不到P类算法的NP类问题,都可以找到相应的P类算法了。

也就代表大整数的质因数分解问题,变成了P类问题。

如2048位二进制大整数,也就可以用一台普通的电脑,在几秒钟,甚至更短的时间内,完成质因数的分解。

如果是这样的话,那现在被广泛应用的RSA加密算法,将彻底失效。

大量的银行数字证书,网站SSL加密,也将不再安全。

那些如今大热的数字货币,也将变成随时可能被取走的移动财富。

整个数字金融,都将大洗牌。

同时,如果NPP的话,也代表那些通过计算很难解决的大量问题,都将通过算法的优化,轻松得到解决。

像是天气的预测,交通的调度,通过氨基酸序列来预测蛋白质结构,计算机芯片上最有效的晶体管布局等等等等的问题,都将得以解决。

毫不夸张的说,这绝对是一个改变世界的难题。

想到这些的陈舟,倒没有因为这些现实意义,变得有多激动。

他只是从草稿纸上收回了目光,转而回到电脑屏幕上。

然后挪动鼠标,点开了第二篇下载好的文献资料。

陈舟之所以这样,倒不是他对解决这一问题后,改变世界的想法,没有憧憬。

实在是,这个问题的难度,着实有点大。

想想也知道,能够被列为七大千禧年大奖难题之一,它的难度会是一般的吗?

而且,从目前学术界的观点来看,绝大多数相关领域的学者,包括数学家、计算理论学家、信息学资深算法研究员等。

都认为NP≠P。

这个问题的难度,由此也可见一斑。

此外