葉華望著幾位學(xué)生微笑：“作為千禧年數(shù)學(xué)七大難題之首的pnp？問(wèn)題到現(xiàn)在也沒(méi)有人能證明或證偽，如果你們有誰(shuí)將來(lái)能解決這個(gè)問(wèn)題就可以立馬去美國(guó)克雷數(shù)學(xué)研究所領(lǐng)取100萬(wàn)美元的賞金，這份懸賞至千禧年宣布至今仍然有效。”
“它既是世界七大數(shù)學(xué)難題之首，但同時(shí)它又是七個(gè)問(wèn)題中最容易理解的一個(gè)數(shù)學(xué)問(wèn)題，其實(shí)就是一個(gè)做數(shù)獨(dú)的問(wèn)題，這個(gè)問(wèn)題誕生于1971年，是理論計(jì)算機(jī)領(lǐng)域誕生的一個(gè)數(shù)學(xué)問(wèn)題。”
教學(xué)是一門(mén)授業(yè)解惑的學(xué)問(wèn)，而葉華可以說(shuō)是一個(gè)無(wú)證教師，不過(guò)這并不妨礙他成為一名合格的講師。
“同學(xué)們，在生活中，你們是怎么去衡量一個(gè)問(wèn)題的？它是簡(jiǎn)單還是復(fù)雜？或者說(shuō)容易還是困難？”葉華在課堂上踱步而走，時(shí)而用余光掃視幾名學(xué)生是否在認(rèn)真聽(tīng)講，什么小動(dòng)作都逃不過(guò)葉校長(zhǎng)的法眼，上課的時(shí)候這幾個(gè)學(xué)生還算乖巧，包括平常愛(ài)搞事的柳玲雙。
片刻便自問(wèn)自答：“這好像沒(méi)有一個(gè)具體的量化標(biāo)準(zhǔn)，而且問(wèn)題還會(huì)因人而異。但是計(jì)算機(jī)不一樣，計(jì)算機(jī)的計(jì)算效率是一個(gè)定值，也沒(méi)有智力商數(shù)。”
“比如兩個(gè)問(wèn)題，一臺(tái)計(jì)算機(jī)從1顯示到10，和從1顯示到1000，顯然后面的問(wèn)題要用到100倍的時(shí)間，相對(duì)前面的問(wèn)題就困難。”
“對(duì)于一臺(tái)計(jì)算機(jī)來(lái)說(shuō)，衡量一個(gè)問(wèn)題的簡(jiǎn)單或困難，看解決問(wèn)題的時(shí)間或者步驟多少，因?yàn)樾试谝欢ǖ那闆r下，時(shí)間和步數(shù)是等價(jià)的，給個(gè)定義就叫時(shí)間復(fù)雜度，時(shí)間復(fù)雜度越小、越少問(wèn)題越簡(jiǎn)單。但實(shí)際情況還得考慮什么？”
說(shuō)完葉華看向了他們幾個(gè)，不一會(huì)兒，柳玲雙便道：“還得考慮計(jì)算機(jī)所占用的空間。”
“回答完全正確。”
黑客少女被表?yè)P(yáng)的暗喜，計(jì)算機(jī)可是本女俠的拿手好戲。
葉華對(duì)她投去了一個(gè)表?yè)P(yáng)的目光，算是獎(jiǎng)勵(lì)了，然后說(shuō)道：“空間問(wèn)題就放一邊，我們今天講時(shí)間問(wèn)題，舉個(gè)例子……”
再也沒(méi)有什么比經(jīng)典的“舉個(gè)栗子”容易理解了。
“一道題，現(xiàn)在我給你出n個(gè)數(shù)，要求選出其中最大的一個(gè)數(shù)，需要多少步？誰(shuí)知道？”
話音剛落，最小的寧杰便飛速應(yīng)答：“n1步。”
“回答正確！”
葉華點(diǎn)點(diǎn)頭，數(shù)學(xué)小天才寧杰這么快答出來(lái)是在他的意料之中，調(diào)出浮空屏幕羅列一串?dāng)?shù)字：“方法其實(shí)很簡(jiǎn)單，先比較前兩個(gè)，取其中最大的數(shù)與第三個(gè)數(shù)進(jìn)行比較，然后取其中最大的數(shù)再與第四個(gè)比較，以此類(lèi)推，取n個(gè)數(shù)就比較n1次。”
“第二道題，還是給出n個(gè)數(shù)，但這道題是要求把n個(gè)數(shù)從大到小依次排序，那又需要多少步呢？”
寧杰再次不假思索的道：“需要n2步。”
葉華再次點(diǎn)頭：“回答正確。寧杰同學(xué)你可以和其他的同學(xué)介紹一下計(jì)算的過(guò)程么？”
寧杰立馬回答：“用剛才的辦法先選出最大數(shù)需要用到n1步，然后選出剩下的所有數(shù)中最大的數(shù)用n2步，類(lèi)推下去就是……一直加到最后的答案就是n2。”
柳玲雙一看很快就看明白了，這不就是計(jì)算機(jī)編程里面的“冒泡法”嘛，黑客少女自然一看就懂，其實(shí)這些都是簡(jiǎn)單問(wèn)題，在場(chǎng)的八個(gè)學(xué)生都能快速理解。
葉華接著講道：“顯然，隨著n的增加，排序問(wèn)題的難度就比之前選最大數(shù)的難度高了。n1當(dāng)這個(gè)n很大的時(shí)候，1可以省略了，有沒(méi)有無(wú)影響，數(shù)量級(jí)就是由n來(lái)決定的，第二個(gè)問(wèn)題時(shí)間的數(shù)量級(jí)是由n^2決定，別的也可以省略，包括系數(shù)。”
說(shuō)到這里葉華調(diào)出一塊模擬黑板的浮空大屏幕，用手指替代粉筆，在色板上點(diǎn)了一下白色，然后在面板上羅列式子：“用漸進(jìn)符號(hào)o表示，第一個(gè)問(wèn)題的計(jì)算量表示為o，第二個(gè)問(wèn)題表示為o。兩個(gè)問(wèn)題一對(duì)比就發(fā)現(xiàn)隨著n的增加o更難一些，這很好理解，因?yàn)閚^2比n大。”
葉華繼續(xù)邊寫(xiě)邊說(shuō)：“n、n^2、n^3等等或者它們的組合就叫多項(xiàng)式，這類(lèi)問(wèn)題就是pnp？問(wèn)題中的p類(lèi)問(wèn)題。那有沒(méi)有更難的問(wèn)題？當(dāng)然有，比如質(zhì)數(shù)問(wèn)題。”
說(shuō)著葉華回頭看向?qū)W生們：“一個(gè)自然數(shù)a是不是質(zhì)數(shù)？解決它需要多少步？笨方法就是挨個(gè)的除，從1開(kāi)始除到a，所以最多用到a步，完整的描述就是：一個(gè)n位數(shù)的自然數(shù)a是不是質(zhì)數(shù)？”
完全代入講師角色的葉華旋即轉(zhuǎn)身在浮空屏幕上繼續(xù)羅列式子：“n位數(shù)的十進(jìn)制數(shù)可以表示：10^n10^，那顯然質(zhì)數(shù)問(wèn)題就是：o，就算是二進(jìn)制數(shù)也是：o，同學(xué)們看，隨著位數(shù)n的增加質(zhì)數(shù)問(wèn)題是不是已經(jīng)呈現(xiàn)指數(shù)上升了？這是很恐怖的上升趨勢(shì)。”
“以上說(shuō)的所有問(wèn)題都有一個(gè)共同點(diǎn)，不管難不難，只要給一個(gè)答案去驗(yàn)證，就會(huì)顯得容易很多，比如說(shuō)：某個(gè)a不是質(zhì)數(shù)，因?yàn)樗梢员贿@個(gè)數(shù)b整除，那驗(yàn)算它就行了，可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行驗(yàn)證。那么所有這類(lèi)問(wèn)題就是np類(lèi)問(wèn)題。”
葉華環(huán)顧八個(gè)學(xué)生，看到他們的眼神中沒(méi)有任何疑惑不解，顯然都理解了，對(duì)于他們的表現(xiàn)很滿意。
“n代表非確定，p和np的標(biāo)準(zhǔn)定義和圖靈機(jī)有關(guān)，p可以在多項(xiàng)式時(shí)間內(nèi)解決問(wèn)題，而np不管難不難但可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證，這是他們兩者的區(qū)別，要注意。那是不是說(shuō)np問(wèn)題要比p類(lèi)問(wèn)題更難？答案否，因?yàn)閜類(lèi)問(wèn)題是屬于np類(lèi)問(wèn)題，這一點(diǎn)也要注意。”
葉華又在學(xué)生們面前踱步而走，有條不紊的講道：“在數(shù)學(xué)上亦或者計(jì)算機(jī)領(lǐng)域，對(duì)于一個(gè)問(wèn)題的困難與否，很大程度取決于計(jì)算方式，計(jì)算機(jī)就是算法，算法是計(jì)算機(jī)的靈魂。即便做數(shù)學(xué)題目也一樣，同一題有的方法簡(jiǎn)單快速，可能就是差一條輔助線的問(wèn)題。”
“前面講的都是死方法，達(dá)到目的就行了。在計(jì)算機(jī)里的術(shù)語(yǔ)叫冒泡法，其復(fù)雜度就是o，開(kāi)發(fā)優(yōu)越算法可以把復(fù)雜度降低，比如快速排序法的復(fù)雜度就是o，顯然要比n^2小，所以在計(jì)算機(jī)領(lǐng)域?qū)τ谝粋�(gè)問(wèn)題的難易看它的算法優(yōu)越與否。”
“那么就不難理解了，人們研究每一個(gè)計(jì)算機(jī)的算法，目的就是把np類(lèi)問(wèn)題降到p類(lèi)問(wèn)題。可問(wèn)題那么多，要找到猴年馬月？那么，既然np問(wèn)題是有一個(gè)共同點(diǎn)的，即，它們都可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證，會(huì)不會(huì)有另一個(gè)共同點(diǎn)？”
葉華自問(wèn)自答：
“所以我們假設(shè)存在一種萬(wàn)能算法，它能把所有的np問(wèn)題降到p類(lèi)問(wèn)題，這就是pnp？問(wèn)題。甚至都可以不用算出這個(gè)萬(wàn)能算法是什么，只要能夠證明或證偽，就可以拿百萬(wàn)大獎(jiǎng)。”
旋即看向了學(xué)生們：“同時(shí)我們會(huì)發(fā)現(xiàn)，在np問(wèn)題中有那么一小類(lèi)問(wèn)題，它們是明顯要比p類(lèi)問(wèn)題難好多好多，在感覺(jué)上這些問(wèn)題是最不可能成為p類(lèi)問(wèn)題的，而且這些問(wèn)題也有一個(gè)共同點(diǎn)，一旦證明其中任何一個(gè)問(wèn)題有一個(gè)優(yōu)越算法能降到p類(lèi)問(wèn)題，那其它的問(wèn)題也都能降到p類(lèi)問(wèn)題，換句話說(shuō)只要證明了其中一個(gè)屬于p，就是pnp。那么這一小類(lèi)問(wèn)題簡(jiǎn)稱(chēng)npc，也就是np完全問(wèn)題。”
葉華講解到這里的時(shí)候大家都能很好的理解，但接下來(lái)的問(wèn)題對(duì)于他們來(lái)說(shuō)就是不那么友好了。
“npc明顯就比p類(lèi)問(wèn)題難，還是舉個(gè)例子，貼近我們生活的，比如一個(gè)美團(tuán)外賣(mài)小哥，他的家住在a點(diǎn)，要去n個(gè)地方送外賣(mài)，n個(gè)地點(diǎn)的兩兩距離都是已知的。那請(qǐng)問(wèn)這個(gè)外賣(mài)小哥如何走遍每一個(gè)地點(diǎn)最后回到家里，保證他所走的路程是最短的呢？”
說(shuō)到這里，葉華停頓了下來(lái)，拿起水杯喝上一口潤(rùn)潤(rùn)嗓子，八個(gè)學(xué)生皺眉思考，其中數(shù)學(xué)天賦最好的寧杰也狐疑不斷。
過(guò)了一段時(shí)間都沒(méi)有人主動(dòng)回答，意料之中的，葉華便說(shuō)道：“這個(gè)題目在于，外賣(mài)小哥他首先就要面臨有多少種行走路線的可能，怎么用數(shù)學(xué)描述？”
學(xué)生們都看向了葉華，后者道：“那顯然，最終的結(jié)果就是n的階乘o。所以就會(huì)看到，這復(fù)雜度可比之前講述到的問(wèn)題大太多太多了，因?yàn)閛2^n，這個(gè)數(shù)比以常數(shù)為底的指數(shù)大太多了。”
葉華旋即轉(zhuǎn)身在浮空屏幕模擬的黑板上滑動(dòng)：“列如19的階乘，看上去感覺(jué)這個(gè)數(shù)不大，但是，列個(gè)式子：191.2110^17，這個(gè)數(shù)大到就算是用現(xiàn)在最牛的經(jīng)典計(jì)算機(jī)假設(shè)他每秒可以排100萬(wàn)次也要排個(gè)三千年左右。所以，外賣(mài)小哥每天送那么多貨，理論上他光是想要找到一條最佳的路線怕是不可能了。”
“但是同學(xué)們注意，這里的困難和簡(jiǎn)單代表的是一種趨勢(shì)，當(dāng)n很小的時(shí)候，人腦的計(jì)算量也能快速計(jì)算出來(lái)，比如數(shù)獨(dú)吧，33的數(shù)獨(dú)那小學(xué)生都會(huì)算，但是同學(xué)們我給你一個(gè)100100試試看？比如100100的方格子，給出幾個(gè)1100的數(shù)字為線索，然后要求把剩下的各自全填滿并保證橫豎都是1100，這個(gè)問(wèn)題就算用當(dāng)今世界最牛的計(jì)算機(jī)也不能快速求出來(lái)。”
“那么顯然，這道題也是npc問(wèn)題，都玩過(guò)掃雷、俄羅斯方塊這些小游戲沒(méi)有？它們也是npc問(wèn)題。”說(shuō)到這里，這一知識(shí)點(diǎn)也講解的差不多了，葉華最后道：
“所以如果能夠證明pnp，那對(duì)全人類(lèi)的貢獻(xiàn)可就大了，比如說(shuō)人體內(nèi)的蛋白折疊復(fù)雜度就是npc問(wèn)題，一旦要是證明了它是個(gè)p……笑什么笑？”
看到柳玲雙噗嗤一笑，葉華故作板臉的瞪了她一眼，這個(gè)小妮子，他算是看出來(lái)了，八個(gè)學(xué)生里面就屬她最皮。
輕咳了下，接著前面的話題說(shuō)道：“……所以只要證明了它是p類(lèi)問(wèn)題，那很多疾病都能迎刃而解，癌癥、艾滋病這些也都不在話下。但是想要證明pnp是相當(dāng)?shù)牟蝗菀祝驗(yàn)槭紫茸C明pnp它就是一道題對(duì)吧？那么問(wèn)題來(lái)了，它本身就是一道npc問(wèn)題……”
仿佛感受到了這個(gè)問(wèn)題帶來(lái)深深地惡意和滿滿的敵意，這個(gè)問(wèn)題果然是秀，不愧是至今都讓全世界的數(shù)學(xué)家束手無(wú)策的世界七大數(shù)學(xué)難題之首。
……
【精彩東方文學(xué) www.nuodawy.com】 提供武動(dòng)乾坤等作品手打文字版最新章節(jié)首發(fā)，txt電子書(shū)格式免費(fèi)下載歡迎注冊(cè)收藏。