第397章 諾特的守恒定律和對稱性

  2000年，一個700萬美元的大獎被設立來求解七個著名數學難題。稱為千禧年大獎難題：P vs NP；


  這是一個關於計算機計算能力的問題，有一定的深度。


  這個問題在1979年提出，也是千禧年七猜想裏最容易理解的問題。


  一開始的電腦算題很慢，但是科學家改進結構之後就變快了。


  但是有些問題，還是很慢，這個問題是因為數學結構特殊。這樣的數學結構，沒有辦法再想出更快的簡便公式。


  很容易知道乘法是可以找到快速解法的，但是下棋就很難找到快速的解法了。


  數學家想知道介於乘法和下棋之間有沒有可以快速的簡便方法。


  P問題是可以用相當快的計算解決的，比如乘法或者是人名排序。


  NP則包含了很多問題，其中有很多複雜的，比如電路設計，給車輛規劃路程，快遞員送快遞最短路程，資料庫等。


  數學家NP中有很多問題也是屬於P的，也就是很多NP問題也是有快速解法的。


  但數學家想知道NP是不是所有問題都屬於P的，或者NP是不是比P更難。這就是PNP問題。


  如果NP=P的話，那很多繁雜的問題就可以被電腦輕鬆解決了。其中就有治療癌症的問題，要研究數量龐大的蛋白質排列，還有密碼破解，經濟學的問題等等。


  NP中數獨填字的問題，做完後可以驗證是否正確。而其他的NP問題就是做出來，連檢查都很困難。比如下棋問題，說出一個好辦法走下一步，但是如何驗證下一步是好辦法？對問題的檢查都需要巨大無比的計算量，大到一台計算機都難以承受。


  而P中檢查問題的時間都比較短。


  而人類都無法確定檢查問題是不是比做出問題來還要複雜？因為數獨有很多種答案，它不是一種答案。


  而如果能快速的驗證答案，是不是也加快了解決答案的速度。


  一個問題越來越強的話，計算難度會不會呈指數級上升？如果隻是正比例上升，那就單純的增加電腦的數量。


  而有的問題則是時間的增加，是一個多項式問題。NP表示的是非確定性多項式的時間。多台電腦同時找一個問題的多個答案，就可以在多項式內找到正確答案。也要討論在最壞情況下解體的步數。


  一般人認為NP比P更多，但這是不是真的？


  其中的P和NP相同的問題為e問題，有數獨、蛋白質折疊、空當接龍、俄羅斯方塊、掃雷等。如果解決了e問題，就解決所有的NP問題。


  PNP問題類型也很多，還有EXP問題，指數類問題等等多種問題。