計算機巨匠系列 [P與NP問題]毀滅世界的計算機猜想

神奇的科普
12粉絲
43 次觀看·2025年11月2日
我有個同事老蔡 為人十分性感
哦不 感性
上大學時人稱數學系林黛玉
上班後午休時看個蠟筆小新
都經常紅眼睛抽鼻子
有次我看他哭大發了
一把鼻涕一把淚的
一問原來他在看劉慈欣的小說《昭文道》
大家沒看過這個小說也沒關系
我給你簡單介紹一下
內容講的是一些最優秀的科學家們
用生命和外星人換取真理的故事
其中有個情節是八位數學家
為了知道費爾瑪和戈德巴赫
兩個猜想的證明過程
一起坦然赴死
就是為這個情節感動哭的
我觸景生情也哭了
老蔡說
沒想到我不是學數學的
居然也能理解為了猜想而現身的偉大
我說我當然理解
因為我知道對數學來說
最重要的是什麼
數學的心臟不是公式
不是概念
也不是定理
而是問題
可以說數學存在的使命
就是提出問題
然後解決問題
有人認為提出數學猜想並解決
純屬數學家的自嗨
對現實世界和人類進程沒用
這想法是完全錯誤的
古希臘幾何學家阿波羅尼烏斯
總結了圓錐曲線理論
1800年後
由德國天文學家開普勒
將其應用於行星軌道理論
數學家加羅華
公元1831年創立群論
100餘年後獲得物理應用
公元1860年創立的矩陣理論
在60年後應用於量子力學
高斯終其一生都在研究非歐幾何
卻抱憾而終
170年後
在誕生之初
看似毫無用處的非歐幾何
卻成為廣義相對論的核心基礎
這些著名數學思想
也許看似對現實無用
但經過千百年寂寞時光等待
人類終究會發現
這原來是某個重要理論的根基
而這個理論會改變世界
所以問題是數學的靈魂
大家好
我是圖靈宇宙
專門調查數字世界裏的有趣故事
今天我們要聊的這位
1982年圖靈獎得主
斯蒂芬·亞瑟·庫克
他獲獎的重要原因
就是提出了一個著名猜想
被譽為21世紀
計算機科學最偉大的猜想之一
實際上該猜想
已經超過計算機科學範疇
成為了一個有基本意義的數學問題
庫克出生於加拿大的
一個富裕中產家庭
父親是個化學家兼教授
大學時庫克主修科學工程學
在選修課中接觸了計算機編程
在這段學習過程中
他憋了個震驚老師一整年的大仗
有次寫作業
庫克作為選修課學生
和別人合作編寫了一個程序
來證明哥德巴克猜想
通過這段經歷
庫克發現數學纔是自己擅長的領域
於是轉到了數學專業
十分專註計算機復雜性的研究
後來又進入哈佛大學數學系
讀完了研究生和博士學位
畢業後
庫克先進入了加利弗尼亞大學
伯克利分校當助理教授
1970年
該大學拒絕了庫克獲得
數學系終身教授職位的申請
於是庫克無縫跳蹈到多倫多大學
就在第二年
他憋了一個震驚世界50年
也讓老東家加州大學
後悔的自殺大逼抖的大仗
他發表了開創性論文
定理證明過程的復雜性
為NP完全性理論奠定了基礎
並引出P NP猜想
P NP問題有多難
有人曾經做了張數學深淵圖
把數學的深度
用海洋的層次去表示
P和NP問題
大概是躺在馬裏亞納海溝
最深處往上數50米的水平
旁邊並排躺著的是黎曼猜想
至於躺在地球溝底的
這幾位大兄弟是啥
拿多維託普學來說
這個其實已經在研究
高維空間的數學了
現在我們把目光
從海底轉向廣闊的海面上
假設你是一位海盜
正在尋找傳說中的寶藏
寶藏分為兩種
一種是P類寶藏
就像加勒比海盜
捷克船長輕松找到的小寶箱
它們藏的並不深
你只需要一張簡單的藏寶圖
和一點時間
就能在島嶼的某個角落找到它們
這些寶藏就像是P的問題
總是能快速找到
第二種是NP類寶藏
它們就像海神伯賽東的三叉戟一樣
隱藏的非常深
需要一系列復雜的挑戰才能找到
也許需要花費數年的時間
去尋找線索
但是一旦有人告訴你
寶藏的確切位置
你就能立刻驗證這個信息是否準確
這些寶藏就像是NP問題
你可能需要很長時間去尋找
但驗證答案卻很快
那麼P和NP類寶藏相比
哪個找起來更難
或者說它們會不會難度是一樣的
假設我們能證明P等於NP
那麼就說明有一種萬能的海盜技巧
能讓所有的NP類寶藏
都像P類寶藏一樣快速找到
也就是說
世界上可能存在著一個終極祕密
一種超級算法
這種算法不需要去辛苦求解
解決復雜的路徑
就能找到最終的正確答案
怎麼去證明
或者證偽P等於NP呢
這裏我們再看看
庫克提出的NP完全理論
NP完全問題
是指NP問題內最難的一類問題
這個問題想要被驗證
那麼計算機需要花費不現實的時間
指數級時間來運行
比如有人告訴你
有個關於永生的終極大寶藏
藏在一個有椰子樹的小島上
但是海洋那麼寬廣
有椰子樹的小島那麼多
你一個一個找下去
搞不好等世界毀滅了都沒找出來
NP完全問題
就是所有NP問題的天花板
在庫克提出NP完全性理論的第二年
就有人證明瞭很難計算的
21個問題屬於NP完全問題
7年後
又有人把NP完全問題的數量
擴大到300個
到現在NP完全問題數量
達到了成千上萬
其中就包括哥德巴赫猜想
從裏面隨便挑一個
並證明它是P問題的話
那麼P等於NP就被解決了
因為這些NP完全問題
是互相等價的
也就是說
如果你能證明太陽的結構
那麼同類可知宇宙中
所有恆星的結構
當你證明瞭P等於NP
確認存在一種超級算法後
圖靈獎就是你的了
數學王冠的名出
哥德巴赫猜想是你的了
千禧年大獎提供的
100萬美金懸賞是你的了
不過這些榮譽
和接下來要面對的新世界相比
可能連指甲蓋都算不上
超級算法的存在
瞬間會給各個科學領域
帶來革命性的進展
如物理學
統籌學
工程學
靜音學
醫學和生物學等
計算機科學會出現超級變成語言
人工智能所有難點也會得到解決
至於數學
數學壓根不存在
因為數學的所有問題
都可以通過計算機驗證的方法
去得到解決
是不是覺得挺好
別急
還有更好的呢
我想超越李白
那麼超級算法
立刻就能寫出來
比李白更好的詩詞
我喜歡莫扎特
那麼超級算法
就能快速合成
最符合人類愛好的音樂
讓我成為莫扎特
創意與藝術
在一個被超級算法統治的世界裏
變得無足輕重
坦白說
真到了那個時候
我們大概沒時間去搞藝術了
因為經濟學不存在了
計算機會預測出
所有股票的漲跌和金融動向
密碼學就不存在了
銀行不再安全
隱私不存在了
上網如同裸奔
從人類壽命到核彈密碼
或是掌握量子糾纏
整個社會資源
被掌握了超級算法的人
大量竊取
整個社會情緒崩塌了
也許你會說證明P等於NP
不等於掌握了超級算法
但其實只要這個預期存在
就足以讓人類社會陷入恐慌
用庫克本人的話來說
如果P等於NP被證偽了
對世界有好的影響
比如能證明加密協議的有效性
如果P等於NP被證明瞭
那麼世界會產生戲劇性的變化
這個戲劇性的變化
也許是說
當我們證明世界
存在一條捷徑的時候
那麼世界就離毀滅不遠了
P與NP問題實在太迷人
太有名
甚至還起立了不少文學藝術創作
比如東野歸吾小說
嫌疑犯X的現身裏
P與NP概念就貫穿始終
比如美版
《瓦爾摩斯電視劇基本演繹法》裏
有兩位研究NP問題的數學家被謀殺了
兇手是同行
因為被害者即將證明P等於NP問題
而兇手的動機
就是為了能獨吞成果
破譯世界上所有的密碼系統
P與NP問題
誕生50年來
吸引了一批又一批的數學家
直到現在
一直在多倫多大學教書的庫克教授
平均每個月郵箱裏都會收到一封來信
是關於NP問題的諮詢問題或者解法的
假如說有一天庫克郵箱裏
收到了P不等於NP的最終證明
那大家該幹嘛幹嘛去
假如他收到了P等於NP的最終證明
那我和在座的各位
恐怕只能抓緊苦練
鑽木取火和廢土求生的技能
也許有人會說
圖靈獎得主
怎麼提了這麼一個
潘多拉魔盒般的猜想
別忘了咱們開頭說的
一個有意義的數學問題
就是人類進步的重要階梯
P與NP問題
其實在多種意義上討論終極問題
在給定時間和空間下
到底什麼可以被計算出來
人類求知的極限又在哪裏
這個問題
也許值得我們在有限的時間裏
用無窮的勇氣和好奇心
去得到解答
我是圖靈宇宙
講有溫度的故事
做有思考的科普
我們下期再見
