他们的表现很满意。

　　“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个地点的两两距离都是已知的。那请问这个外卖小哥如何走遍每一个地点最后回到家里，保证他所走的路程是最短的呢？”

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

　　过了一段时间都没有人主动回答，意料之中的，叶华便说道：“这个题目在于，外卖小哥

　　请收藏：https://m.bqgrr.cc

（温馨提示：请关闭畅读或阅读模式，否则内容无法正常显示）