設置

第322章 NP完全問題的啟示?

熊貓書庫    學霸從改變開始
🔊點這里聽書

  陳舟見此,笑著搖了搖頭。

  他覺得趙琦琦和朱明理,已經徹底達到了放飛自我的境界。

  至于李禮,倒沒有放飛自我。

  一來是他的性格比較內斂,二來,他壓根不具備放飛自我的條件好不好!

  自從他跟李靜在一起后,就一直被李靜管著…

  重新將目光放在電腦網頁上,陳舟滑動鼠標滾輪的手,忽的一頓。

  倒不是因為眼前的內容,而是他忽然想起來,剛才在朱明理手機上看到的那個頭像,怎么那么熟悉?

  “又是張教授?”

  陳舟不由得有些哭笑不得,先前的校園網上的事,他還記得呢。

  但沒想到,這位張中原教授,居然這么喜歡混校園網。

  難道和學生打成一片,才能證明自己一直是年輕的自己嗎?

  也不一定吧?至少那腦袋就不像了…

  “設計一種五邊形,用它鋪滿一個平面而不留下空隙,有多少種這樣的五邊形?”

  這是“平面密鋪”的問題,也是一直困擾數學界的難題。

  密鋪理論的應用有很多,像最簡單的堆放物體時,如何最大利用空間,節省成本。

  在晶體學中,如何優化晶體結構,也屬于密鋪理論的應用范疇。

  但是,因為正五邊形的每個內角為108度,而非360度的因數,所以無法密鋪平面,只能用變形的五邊形挑戰該問題。

  而11件數學界的大事之一,便是數學家終于找到了第15種五邊形。

  這也是陳舟所感興趣的兩件事之一。

  陳舟饒有興趣的看著網頁上15個被五邊形鋪滿的圖案。

  五邊形問題是大多數學家所感興趣的幾何學領域,因為它是唯一一種尚未被完全理解的形狀。

  而這第15種五邊形,也是30年來新發現的首個滿足條件的五邊形。

  陳舟思索了一下,便滑動鼠標,看向下一個感興趣的事件了。

  現在的他,單純的只是興趣,并不打算立即買入幾何學的領域。

  至于,陳舟所感興趣的另一件事,便是圖同構問題的進展。

  這在復雜性理論中一直是一個特殊問題。

  簡單來說,就是一個正五邊形或者是一個五角星,是否屬于同構,也就是點之間一一對應的問題。

  在這件事的描述上,是關于芝加哥大學的Babai教授在2014年研討會上提交的有關論文。

  他的成果旨在表明,解決這個問題只需要比多項式時間略長的擬多項式時間。

  他的成果也被大多數的數學家所認可,認為這將會是這個領域內的巨大進展。

  同時會對價值百萬美元的“P/NP問題”產生啟示。

  沒錯,就是那個七大千禧難題之一的“P/NP問題”。

  和1900年在國際數學家大會上希爾伯特提出的著名的“希爾伯特23問”一樣。

  這是由米國克雷數學研究所,在千禧年5月24日公布的七個世界級數學難題。

  每個難題的獎都是一百萬美元!

  七大千禧難題分別是NP完全問題(P/NP問題)、霍奇猜想、龐加萊猜想、黎曼猜想、楊—米爾斯規范場存在性和質量間隔假設(規范場理論)、NS方程解的存在性與光滑性以及BSD猜想(貝赫和斯維訥通戴爾猜想)。

  目前為止,只有龐加萊猜想被俄羅斯數學家佩雷爾曼所解決。

  “對NP完全問題產生啟示嗎?”

  相比較來說,這11件大事中,這件是令陳舟最感興趣的。

  畢竟是和千禧難題產生關系的研究。

  雖然對很多人來說,可能11件大事中的最后一件,也就是陳舟的事件,更加吸引人的眼球。

  關于NP完全問題,舉個簡單的例子。

  在某個晚上,你去參加了一個宴會。由于宴會過于盛大,你感到了局促不安,這時你會想知道整個宴會廳里,是否有你認識的人。

  恰好這時,宴會的主人向你提議說,你一定認識那位正在甜點盤附近吃冰淇淋的女士。

  幾乎不費多少時間,你就能向那里掃視,并且發現宴會的主人是正確的。

  然而,如果沒有這樣的暗示,你就必須環顧整個宴會廳,一個個地審視每一個人,看是否有你認識的人。

  這其實就像一件事,如果一個人告訴你,12717421可以寫成兩個較小的數的乘積。

  你肯定會遲疑,并且猜想他說的對不對。

  但是,如果他告訴你,12717421可以分解為3607乘上3803,那你很快就能得到答案,并且驗證這是對的。

  這就是NP完全問題的簡單例子。

  至于NP完全問題這個猜想,指的則是既然所有的完全多項式非確定性問題,都可以轉換為一類叫做滿足性問題的邏輯運算問題。

  這類問題的所有可能答案,都可以在多項式時間內計算,那是否這類問題,存在一個確定性算法,可以在多項式時間內,直接算出或是搜尋出正確的答案呢?

  聽著很簡單,但是驗證起來,就完全是另外一回事了。

  NP完全問題也是邏輯和計算機科學中最突出的問題之一。

  即使現在的計算機科學發展迅速,但是這個問題的答案,依然無解。

  輕輕搖了搖頭,陳舟把腦海中的雜亂思緒甩出,不管是不是真的能夠對NP完全問題產生啟示,這位Babai教授的論文,他是必須得看上一看的。

  正好他今天也開始學習計算機科學的知識了。

  把電腦還給李禮,陳舟發現朱明理這小子居然還沒回來,不由得有些哭笑不得,這能是什么秘密,讓他寧跑也要保密?

  “陳哥,那個,能不能請教你個問題?”李禮接過電腦,支支吾吾的說道。

  陳舟看了李禮一眼,旋即拍了拍他的肩膀,笑著說道:“你小子有什么就說?吞吞吐吐的干嘛呢?”

  趙琦琦也湊上來說:“就是,陳哥又不是外人,咋滴,兩個LI,你還生疏了?”

  李禮靦腆一笑:“不是,不是…”

  陳舟看著李禮,想說什么,但最終沒說,只是問道:“是什么問題?”

  李禮拿出自己的筆記本,翻到今天才寫的內容,指了指上面的公式:“是關于分布解構法的,這部分內容,我研究了半天,還是看不明白。”

  陳舟看了一眼,嘴角露出一絲微笑。

高速文字學霸從改變開始章節列表

上一章
書頁
下一章