第一版主 > 网游小说 > 全能科技巨头 > 第552章 这个问题果然是秀啊

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

说到这里叶华调出一块模拟黑板的浮空大屏幕,用手指替代粉笔,在色板上点了一下白色,然后在面板上罗列式子:“用渐进符号o表示,第一个问题的计算量表示为o(n),第二个问题表示为o(n^2)。两个问题一对比就发现随着n的增加o(n^2)更难一些,这很好理解,因为n^2比n大。”

叶华继续边写边说:“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π(ne)^n,这个数比以常数为底的指数大太多了。”

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

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

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

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

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

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

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

……

最新小说: 红雾过后 假如我是beta 獭獭我呀,靠存档振兴乡村 天下有雪 我是林正英的僵尸徒弟 都市神警:从暑假开始的破案天王 末世降临:全球断电 天启之夜 凶宅试睡,我鬼中介的身份被全网曝光 才不是废物!(暂定)
本站公告:点击获取最新地址