<content></p>
（这章大家当学霸来看，如果看不懂当主角装好啦，这一章是为今后生物基因工程做铺垫，大家看完知道了，后面的更新不会出现这种劝退类的章节了，定都定好含着泪也要写完……o(╥﹏╥)o）</p>
——</p>
叶华望着几位学生微笑：“作为千禧年数学七大难题之首的p=np？问题到现在也没有人能证明或证伪，如果你们有谁将来能解决这个问题可以立马去美国克雷数学研究所领取100万美元的赏金，这份悬赏至千禧年宣布至今仍然有效。手机端 m.”</p>
“它既是世界七大数学难题之首，但同时它又是七个问题最容易理解的一个数学问题，其实是一个做数独的问题，这个问题诞生于1971年，是理论计算机领域诞生的一个数学问题。”</p>
教学是一门授业解惑的学问，而叶华可以说是一个无证教师，不过这并不妨碍他成为一名合格的讲师。</p>
“同学们，在生活，你们是怎么去衡量一个问题的？它是简单还是复杂？或者说容易还是困难？”叶华在课堂踱步而走，时而用余光扫视几名学生是否在认真听讲，什么小动作都逃不过叶校长的法眼，课的时候这几个学生还算乖巧，包括平常爱搞事的柳玲双。</p>
片刻便自问自答：“这好像没有一个具体的量化标准，而且问题还会因人而异。但是计算机不一样，计算机的计算效率是一个定值，也没有智力商数。”</p>
“如两个问题，一台计算机从1显示到10，和从1显示到1000，显然后面的问题要用到100倍的时间，相对前面的问题困难。”</p>
“对于一台计算机来说，衡量一个问题的简单或困难，看解决问题的时间或者步骤多少，因为效率在一定的情况下，时间和步数是等价的，给个定义叫时间复杂度，时间复杂度越小、越少问题越简单。但实际情况还得考虑什么？”</p>
说完叶华看向了他们几个，不一会儿，柳玲双便道：“还得考虑计算机所占用的空间。”</p>
“回答完全正确。”</p>
黑客少女被表扬的暗喜，计算机可是本女侠的拿手好戏。</p>
叶华对她投去了一个表扬的目光，算是奖励了，然后说道：“空间问题放一边，我们今天讲时间问题，举个例子……”</p>
再也没有什么经典的“举个栗子”容易理解了。</p>
“一道题，现在我给你出n个数，要求选出其最大的一个数，需要多少步？谁知道？”</p>
话音刚落，最小的宁杰便飞速应答：“n-1步。”</p>
“回答正确！”</p>
叶华点点头，数学小天才宁杰这么快答出来是在他的意料之，调出浮空屏幕罗列一串数字：“方法其实很简单，先较前两个，取其最大的数与第三个数进行较，然后取其最大的数再与第四个较，以此类推，取n个数较n-1次。”</p>
“第二道题，还是给出n个数，但这道题是要求把n个数从大到小依次排序，那又需要多少步呢？”</p>
宁杰再次不假思索的道：“需要n(n-1)/2步。”</p>
叶华再次点头：“回答正确。宁杰同学你可以和其他的同学介绍一下计算的过程么？”</p>
宁杰立马回答：“用刚才的办法先选出最大数需要用到n-1步，然后选出剩下的所有数最大的数用n-2步，类推下去是(n-1)+(n-2)+(n-3)+……一直加到最后的答案是n(n-1)/2。”</p>
柳玲双一看很快看明白了，这不是计算机编程里面的“冒泡法”嘛，黑客少女自然一看懂，其实这些都是简单问题，在场的八个学生都能快速理解。</p>
叶华接着讲道：“显然，随着n的增加，排序问题的难度之前选最大数的难度高了。n-1当这个n很大的时候，-1可以省略了，有没有无影响，数量级是由n来决定的，第二个问题时间的数量级是由n2决定，别的也可以省略，包括系数。”</p>
说到这里叶华调出一块模拟黑板的浮空大屏幕，用手指替代粉笔，在色板点了一下白色，然后在面板罗列式子：“用渐进符号o表示，第一个问题的计算量表示为o(n)，第二个问题表示为o(n2)。两个问题一对发现随着n的增加o(n2)更难一些，这很好理解，因为n2n大。”</p>
叶华继续边写边说：“n、n2、n3等等或者它们的组合叫多项式，这类问题是p=np？问题的p类问题。那有没有更难的问题？当然有，如质数问题。”</p>
说着叶华回头看向学生们：“一个自然数a是不是质数？解决它需要多少步？笨方法是挨个的除，从1开始除到√a，所以最多用到√a步，完整的描述是：一个n位数的自然数a是不是质数？”</p>
完全代入讲师角色的叶华旋即转身在浮空屏幕继续罗列式子：“n位数的十进制数可以表示：10n-10（n-1），那显然质数问题是：o(√102)，算是二进制数也是：o(√2n)，同学们看，随着位数n的增加质数问题是不是已经呈现指数升了？这是很恐怖的升趋势。”</p>
“以说的所有问题都有一个共同点，不管难不难，只要给一个答案去验证，会显得容易很多，如说：某个a不是质数，因为它可以被这个数b整除，那验算它行了，可以在多项式时间内进行验证。那么所有这类问题是np类问题。”</p>
叶华环顾八个学生，看到他们的眼神没有任何疑惑不解，显然都理解了，对于他们的表现很满意。</p>
“n代表非确定，p和np的标准定义和图灵机有关，p可以在多项式时间内解决问题，而np不管难不难但可以在多项式时间内验证，这是他们两者的区别，要注意。那是不是说np问题要p类问题更难？答案否，因为p类问题是属于np类问题，这一点也要注意。”</p>
叶华又在学生们面前踱步而走，有条不紊的讲道：“在数学亦或者计算机领域，对于一个问题的困难与否，很大程度取决于计算方式，计算机是算法，算法是计算机的灵魂。即便做数学题目也一样，同一题有的方法简单快速，可能是差一条辅助线的问题。”</p>
“前面讲的都是死方法，达到目的行了。在计算机里的术语叫‘冒泡法’，其复杂度是o(n2)，开发优越算法可以把复杂度降低，如快速排序法的复杂度是o(nlogn)，显然要n2小，所以在计算机领域对于一个问题的难易看它的算法优越与否。”</p>
“那么不难理解了，人们研究每一个计算机的算法，目的是把np类问题降到p类问题。可问题那么多，要找到猴年马月？那么，既然np问题是有一个共同点的，即，它们都可以在多项式时间内验证，会不会有另一个共同点？”</p>
叶华自问自答：</p>
“所以我们假设存在一种‘万能算法’，它能把所有的np问题降到p类问题，这是p=np？问题。甚至都可以不用算出这个‘万能算法’是什么，只要能够证明或证伪，可以拿百万大奖。”</p>
旋即看向了学生们：“同时我们会发现，在np问题有那么一小类问题，它们是明显要p类问题难好多好多，在感觉这些问题是最不可能成为p类问题的，而且这些问题也有一个共同点，一旦证明其任何一个问题有一个优越算法能降到p类问题，那其它的问题也都能降到p类问题，换句话说只要证明了其一个属于p，是p=np。那么这一小类问题简称np-c，也是np完全问题。”</p>
叶华讲解到这里的时候大家都能很好的理解，但接下来的问题对于他们来说是不那么友好了。</p>
“npc明显p类问题难，还是举个例子，贴近我们生活的，如一个美团外卖小哥，他的家住在a点，要去n个地方送外卖，n个地点的两两距离都是已知的。那请问这个外卖小哥如何走遍每一个地点最后回到家里，保证他所走的路程是最短的呢？”</p>
说到这里，叶华停顿了下来，拿起水杯喝一口润润嗓子，八个学生皱眉思考，其数学天赋最好的宁杰也狐疑不断。</p>
过了一段时间都没有人主动回答，意料之的，叶华便说道：“这个题目在于，外卖小哥他首先要面临有多少种行走路线的可能，怎么用数学描述？”</p>
学生们都看向了叶华，后者道：“那显然，最终的结果是n的阶乘o(n!)。所以会看到，这复杂度可之前讲述到的问题大太多太多了，因为o(n!)≈√2π(n/e)n，这个数以常数为底的指数大太多了。”</p>
叶华旋即转身在浮空屏幕模拟的黑板滑动：“列如19的阶乘，看去感觉这个数不大，但是，列个式子：19!≈1.21x1017，这个数大到算是用现在最牛的经典计算机假设他每秒可以排100万次也要排个三千年左右。所以，外卖小哥每天送那么多货，理论他光是想要找到一条最佳的路线怕是不可能了。”</p>
“但是同学们注意，这里的困难和简单代表的是一种趋势，当n很小的时候，人脑的计算量也能快速计算出来，如数独吧，3x3的数独那小学生都会算，但是同学们我给你一个100x100试试看？如100x100的方格子，给出几个1~100的数字为线索，然后要求把剩下的各自全填满并保证横竖都是1~100，这个问题算用当今世界最牛的计算机也不能快速求出来。”</p>
“那么显然，这道题也是npc问题，都玩过扫雷、俄罗斯方块这些小游戏没有？它们也是npc问题。”说到这里，这一知识点也讲解的差不多了，叶华最后道：</p>
“所以如果能够证明p=np，那对全人类的贡献可大了，如说人体内的蛋白折叠复杂度是npc问题，一旦要是证明了它是个p……笑什么笑？”</p>
看到柳玲双噗嗤一笑，叶华故作板脸的瞪了她一眼，这个小妮子，他算是看出来了，八个学生里面属她最皮。</p>
轻咳了下，接着前面的话题说道：“……所以只要证明了它是p类问题，那很多疾病都能迎刃而解，癌症、艾滋病这些也都不在话下。但是想要证明p=np是相当的不容易，因为首先证明p=np它是一道题对吧？那么问题来了，它本身是一道npc问题……”</p>
仿佛感受到了这个问题带来深深地恶意和满满的敌意，这个问题果然是秀，不愧是至今都让全世界的数学家束手无策的世界七大数学难题之首。</p>
……</content></p>
</p>