七大數學難題1: 能不能行問題 (P=NP?)

    難題一： P=NP?問題 （NP完全問題）

什麽是P=NP?問題，用我的話說，"有些是隻能意會,不能言傳",那請問,"都哪些事是隻能意會,不能言傳呢?" 或者同一問題的另一種問法"都哪些是又可意會,又能言傳呢?"---這兩個問法實際上是一會事，數學家和計算機科學家搞了60年,就希望能知道這個答案.你一看就知道,這個"能不能問題",確實很難! 連說都說不清楚,怎麽可以用數學表述清楚?

Ｐ為多項式算法問題, ＮＰ為非多項式算法問題, 具有確定性多相式時間算法的問題類P是否等於有非確定性多相式時間算法的問題類NP。

這就是“可計算性”裏最著名的NP問題，其全稱為”NP完全問題”(NP COMPLETE)，一般寫作: NP=P？問題。這個問號表明: 到底是NP等於P，還是NP不等於P。
     
由於計算機科學的飛速發展, 可計算性數學的複雜性問題成為諸多數學分支中最為活躍的領域. 其實用性是建立任何一個完整計算係統或證明係統的基礎性問題. 很多可計算/證明問題的複雜性都可以描述為NP問題. 因此NP=P？問題列為七大問題之首就不難理解了。

NP問題: Non-deterministic Polynomial問題, 指的是”多項式複雜性的非確定性問題”。

很多可計算/證明問題的複雜性都可以描述為NP問題, 即問題的複雜性都可以描述/變換為”多項式的複雜性”。

可計算問題的確定性:  比如加減乘除之類，你隻要按照公式推導，按部就班一步步來，就可以得到結果。
    
可計算問題的非確定性: 有些計算問題是無法按部就班直接地計算出來。如，找出大質數的問題, 就找不出一個公式，你一套，就可以推算出下一個質數. 那麽找這個公式的難度或/和找下一個質數的難度是不確定的。這種無法直接計算, 隻能通過間接的“猜算”來得到結果的問題, 就叫非確定性問題。

非確定性問題分為兩種:　對這些不確定的問題，通常存在一個算法．雖然該算法不能直接告訴你答案，但可以告訴你某個可能＂猜＂來的結果是正確還是錯誤。如果這個“猜算”答案正確與否的算法，可以在多項式時間內算出來，就叫做＂多項式非確定性問題＂。如果該問題的所有可能答案，都可以在多項式時間內進行正確與否的計算，那麽這個問題就叫＂完全多項式非確定問題＂。

一般來說，＂完全多項式非確定性問題＂可以用窮舉法得到答案，隻要你一個一個的算下去，最終都能得到所有的結果。但這些算法的複雜程度，是指數性的．也就是說，計算的時間隨著問題的複雜程度成指數性增長，因而變得不可計算了。

五十多年來，數學家和計算機科學家證明了：＂所有的完全多項式非確定性問題，都可以轉換為一類可滿足問題的邏輯演算問題＂。而＂可滿足問題的邏輯演算問題的所有可能答案，都可以在多項式時間內計算＂，於是就猜想，＂是否這類問題存在一個確定性算法，可以在指數時間內直接算出或是搜尋出正確的答案？＂這就是著名的NP=P？猜想。

過去五十多年，為了解決NP=P？猜想，數學家和計算機科學家走了兩條途徑：一是找到一個算法，它是針對某個特定NP完全問題的．找到這個算法，所有這類問題都可解決了，因為所有NP完全問題可以轉化為同一個問題。多數計算機科學家走的都是這條路．另一種，是認為這種算法不存在。那麽就要從數學理論上證明它為什麽不存在。 很多數學家都走這條路．

前兩年幾個印度數學家提出了一個新算法，可以在多項式時間內證明某個數是或者不是質數，打破了人們一直以為質數的證明是非多項式問題。

對P－NP問題,多少數學家和計算機科學家把畢生精力都獻上了. 我國最早的一代可計算性問題專家從80年代初就和國際的發展同步了. 80年代中取得過一些成果. 時至今日, 再無建樹. 可見問題的難度, 應該說, 你覺得有多難---隻要你想得出來, 它就有多難。

------

* 在中國, 每個學科有它的最高學術雜誌, 稱作"xxx學報", 象"數學學報"就是數學界的最高學報,而"代數學報"是數學界代數領域的最高學報...; "物理學報"就是物理學界的最高學報, "量子物理學報"就是物理學界量子領域的最高學報....那麽比各個學界的學報還要高的是"中國科學"---它是中國自然科學界的最高學報.

一般來說,每個學界的學報每月一期, 每期學報有10篇文章. 那麽該學界每年有120篇.
而"中國科學"每三個月出一期,每期學報有10篇文章, 每篇文章來自不同的學界: 一篇數學, 一篇物理, 一篇化學,.... 可見, 全年數學每年最多四篇. 每篇須三個以上學部委員審核簽署.

1986年, "中國科學"有兩篇是關於"可計算性問題的複雜性的". 那都是83, 84, 85研究的結果.