小说620

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

第556章 这个问题果然是秀啊（第2页）

叶华继续边写边说：“n、n2、n3等等或者它们的组合就叫多项式，这类问题就是？问题中的类问题。那有没有更难的问题？当然有，比如质数问题。”

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

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

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

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

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

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

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

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

叶华自问自答：

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

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

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

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

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

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

学生们都看向了叶华，后者道：“那显然，最终的结果就是n的阶乘n。所以就会看到，这复杂度可比之前讲述到的问题大太多太多了，因为n2nen，这个数比以常数为底的指数大太多了。”

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

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

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

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

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

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

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

……nen

她是剑修  大清之百度系统  娱乐：我的粉丝并没有离开  武侠：诸天世界的入侵  Moba：我有一个冠军梦  HP之神话巫师时代  葵花宝典的无限之旅  红楼小相公  我成了非洲狮王  从拜师九叔开始  重生之我实在太凶猛了  玄幻都市之满级天赋  纨绔王妃：病娇王爷狂宠妻  步剑庭  被病娇们喜欢了  DNF从商人开始  上班第一天，我拒绝美女总裁求婚  抖音之最强天王  诡仙寻道  从洪荒开始升级