1975 - 相對化世界：Baker–Gill–Solovay 的衝擊#

案件摘要#

1975 年，Baker、Gill 與 Solovay 發表《Relativizations of the P =? NP Question》，證明存在神諭（oracle）世界裡 P = NP，也存在另一個世界裡 P ≠ NP。這意味著任何「相對化」的證明技術都無法解決原初的 P vs NP——一道禁令，重塑了此後 50 年的攻堅方向。

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

Cook 1971、Karp 1972 建立了 NP-完備理論，但 P vs NP 本身懸而未決。
當時主流嘗試：用「對角化」（diagonalization）與模擬技術——這些技術成功分離了 \(\text{P} \neq \text{EXP}\) 、 \(\text{L} \neq \text{PSPACE}\) 等結果。
邏輯學傳統（Kleene、Post）中「相對於 oracle 的可計算性」早已成熟；Turing 1939 的 oracle 圖靈機是源頭。
核心疑問：對角化這套利器，能不能拿來解 P vs NP？

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

Oracle 圖靈機#

神諭圖靈機 \(M^A\) 可對集合 \(A\) 提問「 \(x \in A\) ?」，並在一個單位步驟內得到答案。定義：

\[ \text{P}^A = \{L : L \text{ 可由某多項式時間 } M^A \text{ 判定}\}, \qquad \text{NP}^A = \{L : L = \{x : \exists y,\ |y| \le p(|x|),\ R^A(x,y)\}\} \]

定理一：存在 oracle \(A\) 使 \(\text{P}^A = \text{NP}^A\)#

取 \(A = \text{PSPACE}\) （或任何 PSPACE-完備的集合，如 TQBF）。因為 \(\text{P}^{\text{PSPACE}} \subseteq \text{PSPACE} = \text{NP}^{\text{PSPACE}} \subseteq \text{P}^{\text{PSPACE}}\) ，故

\[ \text{P}^{\text{PSPACE}} = \text{NP}^{\text{PSPACE}} \]

直觀：oracle 太強，多項式時間的機器可以直接「查表」解掉 NP 完全問題，非決定性失去優勢。

定理二：存在 oracle \(B\) 使 \(\text{P}^B \neq \text{NP}^B\)#

用對角化構造 \(B\) ：把語言定義為

\[ B = \{x_i : M_i^B(x_i) \text{ 拒絕}\} \]

分階段構造：階段 \(i\) 時，挑一個夠長的輸入 \(x_i\) ，把所有長度 \(\le |x_i|\) 、會讓 \(M_i^B\) 在多項式時間內「偷看」的字串都塞進 \(B\) （迫使 \(M_i\) 的計算固定），但把一個關鍵字串 \(y\) 保留在 \(B\) 之外。於是

\[ y \in B \iff \exists \text{ 證書 } w \text{ 使 } (y,w) \in R^B \]

但 \(\text{P}^B\) 機器 \(M_i\) 讀不到 \(y\) 的資訊，必答錯。故 \(\text{P}^B \neq \text{NP}^B\) 。

概念性的 Python 模擬（分階段對角化）：

def build_oracle_B(machines, lengths):
    B = set()
    for i, M in enumerate(machines):
        n = lengths[i]                 # 本階段選定的長度
        # 讓 M^B 在多項式範圍內的查詢結果固定
        queried = simulate_queries(M, B, max_len=n)
        # 選一個 M 查不到的關鍵字串 y
        y = pick_unqueried_string(queried, max_len=n)
        # 設定 y 的成員資格，使 M 必定答錯
        if M_accepts(B, y):
            B.discard(y)               # M 說「在」→ 實際上「不在」
        else:
            B.add(y)                   # M 說「不在」→ 塞進去
    return B

結論：相對化障礙（relativization barrier）#

一個證明技術 \(T\) 是「相對化的」，若對所有 oracle \(A\) ，把 \(T\) 中每個敘述加上上標 \(A\) 後證明仍然成立。Baker–Gill–Solovay 的推論：

**任何相對化的技術，都無法同時證明 \(\text{P} = \text{NP}\) 與 \(\text{P} \neq \text{NP}\) **——因為它在某些世界裡會證出假的結論。

特別是：對角化與模擬技術是相對化的，因此不能解決 P vs NP。

結案 -- 後果與影響#

對角化時代終結：計算複雜度學界被迫尋找「非相對化」技術——必須利用計算模型的具體結構（如電路的有限性），而非黑箱模擬。
自然證明障礙（1994）：Razborov–Rudich 證明，一大類「組合性質」的電路下界技術（自然證明）在存在偽隨機函數生成器的假設下也會失效——第二道禁令。
代數化障礙（2008）：Aaronson–Wigderson 指出「代數化」（algebrization，把 oracle 查詢提升到多項式擴張域）技術也不足以解 P vs NP——第三道禁令，且它精緻化了 BGS 的框架。
三大障礙共同描繪出「攻堅地圖上的雷區」，指引了像 circuit complexity、算術化（arithmeticization, 用於 IP = PSPACE 與 PCP 定理）等非相對化技術的發展。
有趣的哲學餘波：相對化結果也成了「證明技術的分類器」——例如 \(\text{IP} = \text{PSPACE}\) 與 PCP 定理的證明都不相對化，這正是它們深刻的證據。

關鍵人物與文獻#

Theodore Baker、John Gill、Robert Solovay："Relativizations of the P =? NP Question", SIAM J. Comput., 4(4):431–442, 1975。
Alan Turing（1939）：oracle 圖靈機的原始構想（Systems of Logic Based on Ordinals）。
Alexander Razborov、Steven Rudich（1994）："Natural Proofs", STOC 1994 / JCSS 1997。
Scott Aaronson、Avi Wigderson（2008）："Algebrization: A New Barrier in Complexity Theory", STOC 2008。
Baker–Gill–Solovay 論文至今是每本複雜度教科書（Arora–Barak 第 3 章、Sipser）的必備章節。