零点看书

字:
关灯 护眼
零点看书 > 全能科技巨头 > 第556章:这个问题果然是秀啊

第556章:这个问题果然是秀啊

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

叶华环顾八个学生,看到他们的眼神中没有任何疑惑不解,显然都理解了,对于他们的表现很满意。
  
  “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问题……”
  
  仿佛感受到了这个问题带来深深地恶意和满满的敌意,这个问题果然是秀,不愧是至今都让全世界的数学家束手无策的世界七大数学难题之首。
  
  ……
  
  
『加入书签,方便阅读』
热门推荐
我的恐怖猛鬼楼 夏日赞歌 剑道第一棺 为了长生,我挖自家祖坟 修行,从变成反派开始 谁与争锋 最强末日系统 三国之无赖兵王 了不起的盖慈比 仙尊天幽