最新网址:www.83zws.com
首页 > 游戏竞技 > 全能科技巨头 > 第556章:这个问题果然是秀啊

第556章:这个问题果然是秀啊(2/2)

目录
好书推荐: 我在时空管理局工作的日子 后创世录 旺夫小厨娘 淡月梅花 海贼之金色狮鹫 无限征召令 通天武祖 乡村小医圣 我家后院有个修仙界 幻想娱乐帝国

叶华继续边写边说:“n、n^2、n^3等等或者它们的组合就叫多项式,这类问题就是「P=NP?问题」中的P类问题。那有没有更难的问题?当然有,比如质数问题。”

说着叶华回头看向学生们:“一个自然数a是不是质数?解决它需要多少步?笨方法就是挨个的除,从1开始除到√a,所以最多用到√a步,完整的描述就是:一个n位数的自然数a是不是质数?”

完全代入讲师角色的叶华旋即转身在浮空屏幕上继续罗列式子:“n位数的十进制数可以表示:10^n-10^(n-1),那显然质数问题就是:O(√10^2),就算是二进制数也是:O(√2^n),同学们看,随着位数n的增加质数问题是不是已经呈现指数上升了?这是很恐怖的上升趋势。”

“以上说的所有问题都有一个共同点,不管难不难,只要给一个答案去验证,就会显得容易很多,比如说:某个a不是质数,因为它可以被这个数b整除,那验算它就行了,可以在多项式时间内进行验证。那么所有这类问题就是NP类问题。”

叶华环顾八个学生,看到他们的眼神中没有任何疑惑不解,显然都理解了,对于他们的表现很满意。

“N代表非确定,P和NP的标准定义和图灵机有关,P可以在多项式时间内解决问题,而NP不管难不难但可以在多项式时间内验证,这是他们两者的区别,要注意。那是不是说NP问题要比P类问题更难?答案否,因为P类问题是属于NP类问题,这一点也要注意。”

叶华又在学生们面前踱步而走,有条不紊的讲道:“在数学上亦或者计算机领域,对于一个问题的困难与否,很大程度取决于计算方式,计算机就是算法,算法是计算机的灵魂。即便做数学题目也一样,同一题有的方法简单快速,可能就是差一条辅助线的问题。”

“前面讲的都是死方法,达到目的就行了。在计算机里的术语叫‘冒泡法’,其复杂度就是O(n^2),开发优越算法可以把复杂度降低,比如快速排序法的复杂度就是O(nlogn),显然要比n^2小,所以在计算机领域对于一个问题的难易看它的算法优越与否。”

“那么就不难理解了,人们研究每一个计算机的算法,目的就是把NP类问题降到P类问题。可问题那么多,要找到猴年马月?那么,既然NP问题是有一个共同点的,即,它们都可以在多项式时间内验证,会不会有另一个共同点?”

叶华自问自答:

“所以我们假设存在一种‘万能算法’,它能把所有的NP问题降到P类问题,这就是「P=NP?」问题。甚至都可以不用算出这个‘万能算法’是什么,只要能够证明或证伪,就可以拿百万大奖。”

旋即看向了学生们:“同时我们会发现,在NP问题中有那么一小类问题,它们是明显要比P类问题难好多好多,在感觉上这些问题是最不可能成为P类问题的,而且这些问题也有一个共同点,一旦证明其中任何一个问题有一个优越算法能降到P类问题,那其它的问题也都能降到P类问题,换句话说只要证明了其中一个属于P,就是P=NP。那么这一小类问题简称NP-C,也就是NP完全问题。”

叶华讲解到这里的时候大家都能很好的理解,但接下来的问题对于他们来说就是不那么友好了。

“NPC明显就比P类问题难,还是举个例子,贴近我们生活的,比如一个美团外卖小哥,他的家住在A点,要去n个地方送外卖,n个地点的两两距离都是已知的。那请问这个外卖小哥如何走遍每一个地点最后回到家里,保证他所走的路程是最短的呢?”

说到这里,叶华停顿了下来,拿起水杯喝上一口润润嗓子,八个学生皱眉思考,其中数学天赋最好的宁杰也狐疑不断。

过了一段时间都没有人主动回答,意料之中的,叶华便说道:“这个题目在于,外卖小哥他首先就要面临有多少种行走路线的可能,怎么用数学描述?”

学生们都看向了叶华,后者道:“那显然,最终的结果就是n的阶乘O(n!)。所以就会看到,这复杂度可比之前讲述到的问题大太多太多了,因为O(n!)≈√2π(n/e)^n,这个数比以常数为底的指数大太多了。”

叶华旋即转身在浮空屏幕模拟的黑板上滑动:“列如19的阶乘,看上去感觉这个数不大,但是,列个式子:19!≈1.21×10^17,这个数大到就算是用现在最牛的经典计算机假设他每秒可以排100万次也要排个三千年左右。所以,外卖小哥每天送那么多货,理论上他光是想要找到一条最佳的路线怕是不可能了。”

“但是同学们注意,这里的困难和简单代表的是一种趋势,当n很小的时候,人脑的计算量也能快速计算出来,比如数独吧,3×3的数独那小学生都会算,但是同学们我给你一个100×100试试看?比如100×100的方格子,给出几个1~100的数字为线索,然后要求把剩下的各自全填满并保证横竖都是1~100,这个问题就算用当今世界最牛的计算机也不能快速求出来。”

“那么显然,这道题也是NPC问题,都玩过扫雷、俄罗斯方块这些小游戏没有?它们也是NPC问题。”说到这里,这一知识点也讲解的差不多了,叶华最后道:

“所以如果能够证明P=NP,那对全人类的贡献可就大了,比如说人体内的蛋白折叠复杂度就是NPC问题,一旦要是证明了它是个P……笑什么笑?”

看到柳玲双噗嗤一笑,叶华故作板脸的瞪了她一眼,这个小妮子,他算是看出来了,八个学生里面就属她最皮。

轻咳了下,接着前面的话题说道:“……所以只要证明了它是P类问题,那很多疾病都能迎刃而解,癌症、艾滋病这些也都不在话下。但是想要证明P=NP是相当的不容易,因为首先「证明P=NP」它就是一道题对吧?那么问题来了,它本身就是一道NPC问题……”

仿佛感受到了这个问题带来深深地恶意和满满的敌意,这个问题果然是秀,不愧是至今都让全世界的数学家束手无策的世界七大数学难题之首。

……

83中文网最新地址www.83zws.com
目录
新书推荐: 蝴蝶谷传奇 血术士:天启中的魅魔伙伴 诡异复苏:我满身禁忌杀穿诡域 末世:抱歉我的军团只有女兵 诡异入侵:我在末世囤积亿万物资 末世纹身:我为守护神,力挽天倾 异度旅社 黑暗生存游戏 拉格朗日的酒 囤满物资后,女配她在末世躺赢了
返回顶部