第六百七十九章 回到研究狀態（第2/3頁）

也是在一個新的研究課題開始時，陳舟必定會經歷的一個過程。

隨著第一篇文獻資料的下載完成，陳舟移動鼠標，點開了這篇文獻資料。

然後再次拿來草稿紙，擰開筆蓋，準備刷文獻。

NP完全問題，也叫NP－C問題。

是多項式復雜程度的非確定性問題。

簡單的寫法就是“NP=P？”。

問題也就在這個問號上面。

到底是NP等於P，還是NP不等於P。

當然，幾乎絕大多數的人，都希望NP等於P。

因為這背後的實際意義，太過重大。

只可惜，就算再多人的希望，也不能將這道千禧年大獎難題，給變成事實。

它仍舊在等待著，能夠解決它的人出現。

“P類問題和NP類問題的關系……”

第一篇文獻結束，陳舟看了看草稿紙上，自己所寫的內容，小聲的呢喃了一句。

事實上，要知道“NP=P”是個什麽問題，先要知道什麽是P類問題，什麽是NP類問題。

P類問題和NP類問題這兩個概念，是和計算理論中的時間復雜度有關的。

至於計算理論中的時間復雜度，簡單來說，就是解決一個問題的某種算法，所需要的計算量，隨著這個問題的規模增長而增長的速度。

這個概念，更多的被應用在信息學的計算機算法上。

在算法中，時間復雜度本質上，是指計算量增長的速度，而不是這個算法運行的時間。

自然的，對於同樣的一個問題。

如果采用不同的算法，其時間復雜度也是不一定相同的。

而如果某個問題，能夠找到的最優算法的時間復雜度，是n的多項式函數。

那麽，這個問題就被稱之為P類問題。

P也就是多項式的英文首字母。

此外，還有一些問題，無論其是否能夠在多項式時間復雜度內求解，如果知道一個隨便給出的可能解，能夠在多項式時間復雜度內驗證其是否為所求的解。

那麽，這類問題就被稱之為NP類問題。

至於為什麽要研究一個問題，是否有多項式時間復雜度的算法。

則是因為，多項式時間復雜度的計算量增長速度，有些過於“快”了。

隨著n的增大，其計算量遠遠小於O（2^n）、O（n！）、O（n^n）這些時間復雜度問題。

就好比那個很有名的大整數質因數分解問題。

給出一個2048位的二進制整數，要找出它的某個質因數。

一般來說，可能舉全世界的計算能力，也需要上百年的時間，才能完成這個求解計算過程。

但是，如果知道某一個質數的話。

卻可以用最普通的計算機，在幾秒鐘時間內，確定這個質數，是不是這個2048位二進制整數的一個因數。

而這，便是不同時間復雜度，在實際計算過程中的差別！

雖說有時候快了不好，可是在時間復雜度上，還是快一點比較有應用價值。

自然的，全部的P類問題，都屬於NP類問題。

看著草稿紙上的內容，陳舟已經給出了這一顯而易見的解釋。

【一個問題可以在多項式時間復雜度內求解，當然可以在多項式時間復雜度內驗證。】

只不過，寫完這行文字的陳舟，又在下面加了一個“？”。

問號的旁邊，陳舟寫到：“反過來呢？”

沒錯，反過來呢？

一個可以在多項式時間復雜度內驗證的問題，又是否能夠通過多項式時間復雜度的算法求解呢？

陳舟暫時不知道。

所以，他在這個反問的話下面，劃上了兩道橫線。

實際上，這個反問的話，其實也就是，是否全部的NP類問題，都屬於P類問題呢？

而這，便是著名的NP完全問題，也就是“NP=P？”。

陳舟雖然還不知道這個問題的答案。

但是，已經不是信息學小白的陳舟，自然知道這個問題的答案，所具有的現實意義。

如果“NP=P？”沒有了問號。

也就意味著，任何一個原來找不到P類算法的NP類問題，都可以找到相應的P類算法了。

也就代表大整數的質因數分解問題，變成了P類問題。

如2048位二進制大整數，也就可以用一台普通的電腦，在幾秒鐘，甚至更短的時間內，完成質因數的分解。

如果是這樣的話，那現在被廣泛應用的RSA加密算法，將徹底失效。

大量的銀行數字證書，網站SSL加密，也將不再安全。

那些如今大熱的數字貨幣，也將變成隨時可能被取走的移動財富。

整個數字金融，都將大洗牌。

同時，如果NP=P的話，也代表那些通過計算很難解決的大量問題，都將通過算法的優化，輕松得到解決。