數(shù)學(xué)白癡的暴擊：世界十大數(shù)學(xué)難題

　　數(shù)學(xué)這門學(xué)科，對很多學(xué)子來說可能都是一大難題，而對數(shù)學(xué)白癡而言，就可能是相當(dāng)于在看天書了。在當(dāng)今世界中，有十大數(shù)學(xué)難題難住了大部分人，你敢不敢和小編一起去民族文化中感受一下？

　　“千年大獎”七大數(shù)學(xué)難題：
　　1、NP完全問題
　　簡介：
　　NP就是Non-deterministicPolynomial的問題，也即是多項(xiàng)式復(fù)雜程度的非確定性問題。

　　而如果任何一個NP問題都能通過一個多項(xiàng)式時間算法轉(zhuǎn)換為某個NP問題，那么這個NP問題就稱為NP完全問題（Non-deterministicPolynomialcompleteproblem）。NP完全問題也叫做NPC問題。

　　有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導(dǎo)，按部就班一步步來，就可以得到結(jié)果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質(zhì)數(shù)的問題。有沒有一個公式，你一套公式，就可以一步步推算出來，下一個質(zhì)數(shù)應(yīng)該是多少呢？這樣的公式是沒有的。再比如，大的合數(shù)分解質(zhì)因數(shù)的問題，有沒有一個公式，把合數(shù)代進(jìn)去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。

　　這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結(jié)果。這就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什么，但可以告訴你，某個可能的結(jié)果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項(xiàng)式時間內(nèi)算出來，就叫做多項(xiàng)式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項(xiàng)式時間內(nèi)進(jìn)行正確與否的驗(yàn)算的話，就叫完全多項(xiàng)式非確定問題。

　　完全多項(xiàng)式非確定性問題可以用窮舉法得到答案，一個個檢驗(yàn)下去，最終便能得到結(jié)果。但是這樣算法的復(fù)雜程度，是指數(shù)關(guān)系，因此計算的時間隨問題的復(fù)雜程度成指數(shù)的增長，很快便變得不可計算了。

　　人們發(fā)現(xiàn)，所有的完全多項(xiàng)式非確定性問題，都可以轉(zhuǎn)換為一類叫做滿足性問題的邏輯運(yùn)算問題。既然這類問題的所有可能答案，都可以在多項(xiàng)式時間內(nèi)計算，人們于是就猜想，是否這類問題存在一個確定性算法，可以在多項(xiàng)式時間內(nèi)直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。

　　解決這個猜想，無非兩種可能，一種是找到一個這樣的算法，只要針對某個特定NP完全問題找到一個算法，所有這類問題都可以迎刃而解了，因?yàn)樗麄兛梢赞D(zhuǎn)化為同一個問題。另外的一種可能，就是這樣的算法是不存在的。那么就要從數(shù)學(xué)理論上證明它為什么不存在。

　　詳細(xì)信息：
　　P類問題：所有可以在多項(xiàng)式時間內(nèi)求解的判定問題構(gòu)成P類問題。判定問題：判斷是否有一種能夠解決某一類問題的能行算法的研究課題。

　　NP類問題：所有的非確定性多項(xiàng)式時間可解的判定問題構(gòu)成NP類問題。非確定性算法：非確定性算法將問題分解成猜測和驗(yàn)證兩個階段。算法的猜測階段是非確定性的，算法的驗(yàn)證階段是確定性的，它驗(yàn)證猜測階段給出解的正確性。設(shè)算法A是解一個判定問題Q的非確定性算法，如果A的驗(yàn)證階段能在多項(xiàng)式時間內(nèi)完成，則稱A是一個多項(xiàng)式時間非確定性算法。有些計算問題是確定性的，例如加減乘除，只要按照公式推導(dǎo)，按部就班一步步來，就可以得到結(jié)果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質(zhì)數(shù)的問題。有沒有一個公式能推出下一個質(zhì)數(shù)是多少呢？這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結(jié)果。這也就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什么，但可以告訴你，某個可能的結(jié)果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項(xiàng)式（polynomial）時間內(nèi)算出來，就叫做多項(xiàng)式非確定性問題。

　　NPC問題：NP中的某些問題的復(fù)雜性與整個類的復(fù)雜性相關(guān)聯(lián).這些問題中任何一個如果存在多項(xiàng)式時間的算法,那么所有NP問題都是多項(xiàng)式時間可解的.這些問題被稱為NP-完全問題(NPC問題)。

　　例子：
　　在一個周六的晚上，你參加了一個盛大的晚會。由于感到局促不安，你想知道這一大廳中是否有你已經(jīng)認(rèn)識的人。宴會的主人向你提議說，你一定認(rèn)識那位正在甜點(diǎn)盤附近角落的女士羅絲。不費(fèi)一秒鐘，你就能向那里掃視，并且發(fā)現(xiàn)宴會的主人是正確的。然而，如果沒有這樣的暗示，你就必須環(huán)顧整個大廳，一個個地審視每一個人，看是否有你認(rèn)識的人。

　　生成問題的一個解通常比驗(yàn)證一個給定的解時間花費(fèi)要多得多。這是這種一般現(xiàn)象的一個例子。與此類似的是，如果某人告訴你，數(shù)13717421可以寫成兩個較小的數(shù)的乘積，你可能不知道是否應(yīng)該相信他，但是如果他告訴你它可以分解為3607乘上3803，那么你就可以用一個袖珍計算器容易驗(yàn)證這是對的。

　　人們發(fā)現(xiàn)，所有的完全多項(xiàng)式非確定性問題，都可以轉(zhuǎn)換為一類叫做滿足性問題的邏輯運(yùn)算問題。既然這類問題的所有可能答案，都可以在多項(xiàng)式時間內(nèi)計算，人們于是就猜想，是否這類問題，存在一個確定性算法，可以在多項(xiàng)式時間內(nèi)，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。

　　不管我們編寫程序是否靈巧，判定一個答案是可以很快利用內(nèi)部知識來驗(yàn)證，還是沒有這樣的提示而需要花費(fèi)大量時間來求解，被看作邏輯和計算機(jī)科學(xué)中最突出的問題之一。它是斯蒂文·考克于1971年陳述的。

你可能也喜歡：
十大最有氣質(zhì)的樂器，讓你散發(fā)迷人氣質(zhì)
中國四大兇獸，一個比一個兇
上古十大魔神都有哪些，上古十大魔神誰最厲害
中國古代十大美男簡介，古代十大美男復(fù)原圖