北京時間7月4日消息，「P對NP」問題一直是全球七大數學難題之一。美國麻薩諸塞州克雷數學研究所為此設立了專項獎金，能夠證明或反駁這一猜想可以獲得100萬美元的獎金。但如果有人能夠證明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或「有界誤差量子多項式時間」問題。