从P vs NP到量子计算 | Avi Wigderson | 图灵奖&阿贝尔奖得主 | 计算复杂性类 | 布尔可满足性 | NP完全问题 | PCP定理 | 多带图灵机 | 零知识证明 | 格问题

P與NP問題是理論計算機科學最基礎的難題。NP問題的核心定義極其簡單：若他人給出答案，我們能在合理時間內驗證其正確性，該問題就屬於NP。相比之下，P問題要求算法無需外部提示即可自主求解。P與NP問題本質追問：這兩個集合是否相等？若P=NP，人類所有可驗證的難題都能被快速求解，科技會迎來指數級飛躍。但多數科學家相信P≠NP，理由是過去數十年全球頂尖研究者尋找NP完全問題的高效解法而一無所獲。

NP完全問題的關鍵性在於其普遍連結性。所有NP問題都能轉化為布爾可滿足性問題，進而轉化為旅行商問題、數獨、圖著色等看似無關的問題。這種萬能翻譯的屬性讓NP完全問題成為整個領域的焦點。然而理論上的無解不等於現實無解：NP完全問題定義的難度針對最壞輸入場景，而現實工作中遇到的輸入往往不是極端案例。蛋白質折叠雖理論上難度等同NP困難問題，但自然進化已篩選出可控難度的蛋白質。

計算領域的時間與空間資源藏著半世紀的深刻關聯。傳統認知中，執行N步運算最多需要N個存儲單元。但1975年的理論將空間上界壓縮至時間除以對數時間。最近突破性進展來自2025年2月：麻省理工的瑞安威廉姆斯證明空間可進一步壓縮至時間的平方根，打破了50年的理論上界。巴林頓定理提供了另一個反直覺的例子：通過非交換代數的排列運算，只需常數比特工作空間即可完成任意長比特序列的多數表決。

計算難題的難度本身可轉化為隨機性資源。布鲁姆與米卡利的思想實驗闡明：隨機性不是事件的固有屬性，而是觀察者與事件的關係。同一枚硬幣，計算能力弱的觀察者看到隨機性，超級計算機能精準預測其結果。基於此邏輯，NP難問題的不可預測性等同於伪隨機源。NW生成器的精妙之處在於：用十幾比特的真隨機種子，通過多次採樣困難函數的輸出，膨脹出成千上萬的伪隨機比特。這套機制推導出P=BPP，表明依賴隨機數運行的概率算法都有等效的確定性版本。

零知識證明是複雜性理論最優美的應用。該技術的核心約束是：驗證者在確認命題真實後，卻無法獲取任何證明細節。圖三著色協議演示了其原理：證明者密碼學承諾圖的著色方案，驗證者隨機選邊要求展示端點顏色。若圖無法合法著色，驗證者最終必將抽中違規邊；若著色合法且顏色被隨機重排，驗證者每輪只見到兩個不同隨機色，無法提取原始信息。1986年阿維維格德森等人證明了零知識證明的普遍性定理：所有可數學證明的命題都可構建對應的零知識交互式證明。

量子計算成為現代密碼體系最大威脅。1994年Shor算法能高效完成大整數分解與離散對數求解，而這兩類問題正是現有公鑰密碼的安全核心。一旦成熟通用量子計算機面世，全球網路安全體系將瓦解。後量子密碼學的核心目標是尋找量子計算也無法破解的數學難題。格問題因其高維幾何複雜性，至今無已知的高效量子算法，成為後量子密碼學的主流選擇。2020年的重磅結論是MIP*=RE：擁有量子糾纏的多證明者系統能幫助經典驗證者驗證停機問題等原本不可計算的命題，這一發現同時解決了多個數學與物理領域的懸置猜想。