數學白痴的暴擊:世界十大數學難題
2023-07-04 03:13:59 1
數學這門學科,對很多學子來說可能都是一大難題,而對數學白痴而言,就可能是相當於在看天書了。在當今世界中,有十大數學難題難住了大部分人,你敢不敢和小編一起去民族文化中感受一下?
「千年大獎」七大數學難題:
1、NP完全問題
簡介:
NP就是Non-deterministicPolynomial的問題,也即是多項式複雜程度的非確定性問題。
而如果任何一個NP問題都能通過一個多項式時間算法轉換為某個NP問題,那麼這個NP問題就稱為NP完全問題(Non-deterministicPolynomialcompleteproblem)。NP完全問題也叫做NPC問題。
有些計算問題是確定性的,比如加減乘除之類,你只要按照公式推導,按部就班一步步來,就可以得到結果。但是,有些問題是無法按部就班直接地計算出來。比如,找大質數的問題。有沒有一個公式,你一套公式,就可以一步步推算出來,下一個質數應該是多少呢?這樣的公式是沒有的。再比如,大的合數分解質因數的問題,有沒有一個公式,把合數代進去,就直接可以算出,它的因子各自是多少?也沒有這樣的公式。
這種問題的答案,是無法直接計算得到的,只能通過間接的「猜算」來得到結果。這就是非確定性問題。而這些問題的通常有個算法,它不能直接告訴你答案是什麼,但可以告訴你,某個可能的結果是正確的答案還是錯誤的。這個可以告訴你「猜算」的答案正確與否的算法,假如可以在多項式時間內算出來,就叫做多項式非確定性問題。而如果這個問題的所有可能答案,都是可以在多項式時間內進行正確與否的驗算的話,就叫完全多項式非確定問題。
完全多項式非確定性問題可以用窮舉法得到答案,一個個檢驗下去,最終便能得到結果。但是這樣算法的複雜程度,是指數關係,因此計算的時間隨問題的複雜程度成指數的增長,很快便變得不可計算了。
人們發現,所有的完全多項式非確定性問題,都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案,都可以在多項式時間內計算,人們於是就猜想,是否這類問題存在一個確定性算法,可以在多項式時間內直接算出或是搜尋出正確的答案呢?這就是著名的NP=P?的猜想。
解決這個猜想,無非兩種可能,一種是找到一個這樣的算法,只要針對某個特定NP完全問題找到一個算法,所有這類問題都可以迎刃而解了,因為他們可以轉化為同一個問題。另外的一種可能,就是這樣的算法是不存在的。那麼就要從數學理論上證明它為什麼不存在。
詳細信息:
P類問題:所有可以在多項式時間內求解的判定問題構成P類問題。判定問題:判斷是否有一種能夠解決某一類問題的能行算法的研究課題。
NP類問題:所有的非確定性多項式時間可解的判定問題構成NP類問題。非確定性算法:非確定性算法將問題分解成猜測和驗證兩個階段。算法的猜測階段是非確定性的,算法的驗證階段是確定性的,它驗證猜測階段給出解的正確性。設算法A是解一個判定問題Q的非確定性算法,如果A的驗證階段能在多項式時間內完成,則稱A是一個多項式時間非確定性算法。有些計算問題是確定性的,例如加減乘除,只要按照公式推導,按部就班一步步來,就可以得到結果。但是,有些問題是無法按部就班直接地計算出來。比如,找大質數的問題。有沒有一個公式能推出下一個質數是多少呢?這種問題的答案,是無法直接計算得到的,只能通過間接的「猜算」來得到結果。這也就是非確定性問題。而這些問題的通常有個算法,它不能直接告訴你答案是什麼,但可以告訴你,某個可能的結果是正確的答案還是錯誤的。這個可以告訴你「猜算」的答案正確與否的算法,假如可以在多項式(polynomial)時間內算出來,就叫做多項式非確定性問題。
NPC問題:NP中的某些問題的複雜性與整個類的複雜性相關聯.這些問題中任何一個如果存在多項式時間的算法,那麼所有NP問題都是多項式時間可解的.這些問題被稱為NP-完全問題(NPC問題)。
例子:
在一個周六的晚上,你參加了一個盛大的晚會。由於感到局促不安,你想知道這一大廳中是否有你已經認識的人。宴會的主人向你提議說,你一定認識那位正在甜點盤附近角落的女士羅絲。不費一秒鐘,你就能向那裡掃視,並且發現宴會的主人是正確的。然而,如果沒有這樣的暗示,你就必須環顧整個大廳,一個個地審視每一個人,看是否有你認識的人。
生成問題的一個解通常比驗證一個給定的解時間花費要多得多。這是這種一般現象的一個例子。與此類似的是,如果某人告訴你,數13717421可以寫成兩個較小的數的乘積,你可能不知道是否應該相信他,但是如果他告訴你它可以分解為3607乘上3803,那麼你就可以用一個袖珍計算器容易驗證這是對的。
人們發現,所有的完全多項式非確定性問題,都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案,都可以在多項式時間內計算,人們於是就猜想,是否這類問題,存在一個確定性算法,可以在多項式時間內,直接算出或是搜尋出正確的答案呢?這就是著名的NP=P?的猜想。
不管我們編寫程序是否靈巧,判定一個答案是可以很快利用內部知識來驗證,還是沒有這樣的提示而需要花費大量時間來求解,被看作邏輯和計算機科學中最突出的問題之一。它是斯蒂文·考克於1971年陳述的。