1956-Gödel 的信件#

案件摘要#

1956 年 3 月 20 日，Kurt Gödel 寫給病中的 John von Neumann 一封短信，首次提出「以計算步驟數（或字母長度）衡量問題難度」，並問：SAT 型問題能否以線性、二次或類似的多項式時間解決？這封信沉睡 32 年，直到 1988 年才被發現——它比 Cook 的 P vs NP 早了 15 年。

前因 -- 為什麼會有這個案子#

1930 年代，Gödel 以不完備定理震驚邏輯學界（1931），但他的興趣一直延伸到「證明的長度」「計算的複雜度」——他 1936 年就發表過關於算術命題最短證明長度可任意增長的注記。
1950 年代，von Neumann 已病重（1955 年確診癌症，1957 年去世），兩位巨人以書信保持智力交流。
Gödel 的偵探直覺：既然可判定性（是否有演算法）已由 Turing 解決，下一個問題自然是演算法的效率——「需要多少步驟」。這是從遞迴論跨向複雜度理論的第一步。

線索與推理 -- 數學式、程式、理論#

信的內容#

Gödel 於 1956 年 3 月 20 日致 von Neumann（德文原文，1988 年由 Juris Hartmanis 發現並譯出）。信中關鍵段落（意譯）：

「可以抽象地設想一類問題：給定一個命題，其否定可由有限組合實驗確定（例如可逐一代入有限多個變數的值來檢驗）。顯然，若要回答『是或否』，只需嘗試有限多種可能——但所需步驟數可能隨問題長度增長得非常快。現在問題是：這個過程能否透過更好的方法大幅縮短？例如能否以線性、二次或類似限制的步驟數解決？」

Gödel 特別舉了「命題演算的滿足性」為例——正是今天的 SAT 問題。他問：是否存在演算法，使其步驟數為 \(O(n)\) 或 \(O(n^2)\) （ \(n\) 為公式長度）？

以步驟數衡量問題難度：首次的複雜度量測#

信的核心貢獻是概念的：

\[ \text{問題難度} = \min_{M \text{ 解決此問題}} \{\text{步驟數 } T_M(n)\} \]

即「解決長度為 \(n\) 的實例所需的最少步驟數（取最優演算法）」。這是現代時間複雜度 \(T(n)\) 定義的雛形，也是「按難度給問題分級」思想的第一次明確表述。

Gödel 進一步指出：若這類問題無法用線性/二次時間解決，這將是「最重要的結果」——因為它意味著某些問題本質上需要暴力搜尋，再聰明的數學也繞不過去。

SAT 型問題#

Gödel 信中的例子正是布爾可滿足性問題（SAT）：給定命題邏輯公式 \(\varphi\) ，是否存在真值賦值使其為真？

\[ \varphi = \bigwedge_{i} \bigvee_{j} \ell_{ij}, \quad \ell_{ij} \in \{x_1, \neg x_1, \ldots, x_n, \neg x_n\} \]

暴力解法需要 \(2^n\) 次嘗試。Gödel 問：能否做到 \(O(n^k)\) （某固定 \(k\) ）？以今日語言：SAT 是否屬於 P？ 而 Cook–Levin 定理告訴我們，這等價於 P vs NP：

\[ \text{SAT} \in \text{P} \iff \text{P} = \text{NP} \]

這封信 1988 年才被發現#

信件寫於 1956 年，夾在 Gödel 的遺稿中，長期無人知曉。
1988 年，複雜度理論先驅 Juris Hartmanis（圖靈獎 1993）在普林斯頓檔案中發現此信，將其譯成英文並發表（Some observations about the nature of computer science 等場合介紹）。
發現時機微妙：當時 P vs NP 已是電腦科學的頭號難題，這封信證明 Gödel 早於 Cook 15 年就精確提出了問題核心——歷史被改寫：P vs NP 的「最初提出者」應追溯至 Gödel 1956。

Gödel 預見了 P vs NP；與 Cook 1971 的獨立路線#

面向	Gödel 1956 信	Cook 1971 論文
提出的問題	SAT 能否線性/二次時間解決？	SAT 是否 NP-完備？P vs NP 的框架化
概念工具	步驟數 \(T(n)\) 作為難度度量	多項式時間歸約、NP-完備性
方法論	書信中的孤立洞見	系統性理論（Cook–Levin 定理）
結局	未公開、未發展	成為複雜度理論的奠基論文

兩條路線完全獨立：Cook 在 1971 年提出 NP-完備性時並不知道 Gödel 的信；Gödel 在 1956 年也沒有 NP、多項式歸約這些工具。這是科學史上罕見的「同一問題、兩位巨人、獨立發現」案例——就像 Newton 與 Leibniz 的微積分，只不過這次是書信與論文，相隔 15 年。

Python 演示 Gödel 信中的核心對比：

from itertools import product

def sat_brute_force(clauses, n_vars):
    """暴力解 SAT：O(2^n * |formula|) —— Gödel 擔心的『步驟數爆炸』"""
    for assignment in product([True, False], repeat=n_vars):
        if all(any(assignment[abs(lit)-1] == (lit > 0) for lit in c)
               for c in clauses):
            return True
    return False

def formula_length(clauses, n_vars):
    """公式長度 n：Gödel 的『字母長度』度量"""
    return sum(len(c) for c in clauses) + n_vars

# Gödel 的問題（今日語言）：是否存在 sat_solve(n) = O(n^k) 的演算法？
# - 暴力法：T(n) ~ 2^(n_vars)，步驟數隨長度指數增長
# - 目前無人找到多項式時間演算法，也無人能證明不存在（P vs NP 開放）
clauses = [[1, 2], [-1, 3], [2, -3]]
print(sat_brute_force(clauses, 3))   # True，但付出了 2^3 次嘗試

歷史意義#

這封信標記了計算理論的範式轉移：從「可計算性」（是否能算）到「複雜度」（要算多久）。
Gödel 對「組合爆炸 vs 更聰明的方法」的提問，正是 P vs NP 的哲學核心：驗證容易，尋找是否也容易？
信中對「線性、二次」等具體多項式界的強調，預示了 Cobham–Edmonds（1964/65）對「多項式時間 = 可行計算」的形式化定義。
Hartmanis 的發現提醒我們：科學史的斷代有時取決於檔案何時被打開——1956 年的信讓 P vs NP 的前史整整提前了 15 年。

結案 -- 後果與影響#

結案：信件 1988 年出土，確認 Gödel 是「以步驟數衡量難度」與 SAT 效率問題的第一位提出者；P vs NP 的前史追溯至 1956。
Cook 1971 的 NP-完備性理論仍是複雜度理論的正式起點，但 Gödel 的信提供了哲學上的先聲。
深遠影響：P vs NP 成為 Clay 研究所七大千禧年難題之首（2000 年懸賞百萬美元）；Gödel 信中的「組合爆炸本質」問題，至今在密碼學（RSA 的安全性假設）、AI（P vs NP 與搜尋問題）、最佳化理論中持續發酵。
這封信也見證了 20 世紀兩位最偉大邏輯學家/數學家的友誼：von Neumann 收信時已臥病，於次年 1957 年去世——這封短信成為兩人智力對話的絕筆之一。

關鍵人物與文獻#

Kurt Gödel（1906–1978）：不完備定理作者；1956 年 3 月 20 日致 von Neumann 信，P vs NP 的先聲。
John von Neumann（1903–1957）：收信人，電腦架構與賽局理論的奠基者。
Juris Hartmanis（1928–2022）：1988 年發現並譯介此信，複雜度理論先驅（圖靈獎 1993，與 Stearns 共同獲得，表彰時間階層理論）。
Stephen Cook：1971 年《The Complexity of Theorem-Proving Procedures》，NP-完備性理論（圖靈獎 1982）。
Leonid Levin：1971 年蘇聯側獨立發現 NP-完備性。
Alan Cobham / Jack Edmonds：1964/65 年確立「多項式時間 = 有效計算」的標準定義。
原件現藏於美國國會圖書館 Gödel Papers（Princeton/IAS 檔案），Hartmanis 1989 年發表譯文與分析。