把全世界的比特幣收入囊中?請解開“P對NP”難題


正如理論計算機科學家斯科特·阿倫森(Scott Aaronson)上週在新墨西哥州洛斯阿拉莫斯國家實驗室(Los Alamos National Lab)發表的演講那樣,證明P=NP將開啟一些有趣的可能性。 P與NP的重要性主要在於它對計算的影響。

“P”指的是計算機一直在解決的問題,從簡單的兩位數字相乘到更複雜的任務,比如瀏覽互聯網等。當一個問題變得越來越複雜時,解決它所需的時間就會以“多項式時間”增長,多項式是一個具有冪和係數的數字(比如n2)。如果一個問題在n2時間內解決,並且把輸入的規模增加一倍,那麼解決問題所需的時間就會增加四倍。

阿倫森幽默地表示,“如果有人證明P=NP,他們應該做的第一件事就是挖走2000億美元的比特幣。第二件事是解決所有其他千禧年獎難題。”

要理解這一點,人們必須明白計算機是解決問題的設備,根據計算機科學之父艾倫·圖靈(Alan Tling)提出的原則,抽象為物理計算設備可讀的代碼。解決問題需要大量的步驟和一定的時間,隨著問題的增加,所需的時間也會增加。

然而,在許多問題中,人們可以確定一個給定的答案在多項式時間內是正確的,但實際上,在多項式時間內得到這個答案可能性卻是開放的,也許可以,也許不可以。這些問題稱為“不確定多項式時間”或NP問題。數獨就是一個NP問題,很難解決但卻很容易核對結果。今天的另一個重要例子是分解質數。就目前而言,把一個很大的數分解成質數需要很長時間,比多項式時間還要久,但是檢查答案是否正確就如同把所得的數字相乘一樣簡單。事實上,這正是現代加密技術的基礎,現代加密技術依賴於生成易於驗證但難以破解的安全密鑰。

新的數學證明已經發現,並可能繼續找到這些NP問題的P解。 P對NP問題實際上是指,是否每個NP問題都有一個P解,或者是否存在通過P絕對不能解決的NP問題。雖然P≠NP看似顯而易見,但它並沒有經過嚴格的數學證明。如果能夠證明P=NP意味著多項式時間算法適用於很多非常重要的計算機問題,屆時揭開比特幣的神秘面紗顯然不再是件難事兒,畢竟比特幣挖掘和安全密鑰都依賴於難以解決卻易於驗證的NP問題。

量子計算機的數學基礎與經典計算機不同,不能保證每一個NP問題都有P解。人們曾經認為,這類計算機可能解決NP問題中最難攻堅的一類,即“NP完全問題”。如果你能找到這些問題的一個有效解,你就能找到所有NP問題的有效解。這包括“旅行推銷員問題”和許多其他類似的優化問題,但量子計算機並沒有達到這種程度。相反,量子計算機可以在較短的時間內(比如採用一個較低的多項式)解決一些P問題,或者將一些NP問題轉移到P的量子泛化中,後者被稱為BQP或“有界誤差量子多項式時間”問題。

.

Leave a Comment