文学驿站

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

第503章 千禧年七猜想之一 pnp问题XinShuHaiGE CoM（第1页）

一秒记住【m.xiaoyanwenxue.cc】精彩无弹窗免费！

“数学大帝（.shg.tw）”

！

2000年，一个700万美元的大奖被设立来求解七个著名数学难题。

称为千禧年大奖难题：PvsNP；

这是一个关于计算机计算能力的问题，有一定的深度。

这个问题在1979年提出，也是千禧年七猜想里最容易理解的问题。

一开始的电脑算题很慢，但是科学家改进结构之后就变快了。

但是有些问题，还是很慢，这个问题是因为数学结构特殊。

这样的数学结构，没有办法再想出更快的简便公式。

很容易知道乘法是可以找到快速解法的，但是下棋就很难找到快速的解法了。

数学家想知道介于乘法和下棋之间有没有可以快速的简便方法。

P问题是可以用相当快的计算解决的，比如乘法或者是人名排序。

NP则包含了很多问题，其中有很多复杂的，比如电路设计，给车辆规划路程，快递员送快递最短路程，资料库等。

数学家NP中有很多问题也是属于P的，也就是很多NP问题也是有快速解法的。

但数学家想知道NP是不是所有问题都属于P的，或者NP是不是比P更难。

这就是PNP问题。

如果NP=P的话，那很多繁杂的问题就可以被电脑轻松解决了。

其中就有治疗癌症的问题，要研究数量庞大的蛋白质排列，还有密码破解，经济学的问题等等。

NP中数独填字的问题，做完后可以验证是否正确。

而其他的NP问题就是做出来，连检查都很困难。

比如下棋问题，说出一个好办法走下一步，但是如何验证下一步是好办法？对问题的检查都需要巨大无比的计算量，大到一台计算机都难以承受。

而P中检查问题的时间都比较短。

而人类都无法确定检查问题是不是比做出问题来还要复杂？因为数独有很多种答案，它不是一种答案。

而如果能快速的验证答案，是不是也加快了解决答案的速度。

一个问题越来越强的话，计算难度会不会呈指数级上升？如果只是正比例上升，那就单纯的增加电脑的数量。

而有的问题则是时间的增加，是一个多项式问题。

NP表示的是非确定性多项式的时间。

多台电脑同时找一个问题的多个答案，就可以在多项式内找到正确答案。

也要讨论在最坏情况下解体的步数。

一般人认为NP比P更多，但这是不是真的？

其中的P和NP相同的问题为NP-plete问题，有数独、蛋白质折叠、空当接龙、俄罗斯方块、扫雷等。

如果解决了NP-plete问题，就解决所有的NP问题。

PNP问题类型也很多，还有EXP问题，指数类问题等等多种问题。