第322章 NP完全問題的啟示？（2/2）

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

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

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

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

「對NP完全問題產生啟示嗎？」

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

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

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

關於NP完全問題，舉個簡單的例子。

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

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

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

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

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

你肯定會遲疑，並且猜想他說的對不對。

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

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

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

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

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

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

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

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

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

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

「陳哥，那個，能不能請教你個問題？」李禮接過電腦，支支吾吾的說道。

陳舟看了李禮一眼，旋即拍了拍他的肩膀，笑著說道：「你小子有什麼就說？吞吞吐吐的幹嘛呢？」

趙琦琦也湊上來說：「就是，陳哥又不是外人，咋滴，兩個LI，你還生疏了？」

李禮靦腆一笑：「不是，不是……」

陳舟看著李禮，想說什麼，但最終沒說，只是問道：「是什麼問題？」

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

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