跳轉到

5.1 1965 Hartmanis–Stearns 時間階層定理#

前言：可計算之後，問「多快」#

1950 年代末，可計算性理論的版圖已定：哪些問題有演算法解、哪些永遠沒有，已有系統的方法（第 4 章）。但工程師立刻意識到一個尷尬：可判定不等於可實用。一個需要 \(2^{2^n}\) 步的「演算法」對任何實務都毫無意義。

1965 年，Jürgis Hartmanis 與 Richard Stearns 發表〈論多帶圖靈機的計算複雜性〉，首次系統地提出「以計算資源（時間步數）為函數給問題分類」的綱領，並證明了第一個階層定理：

定理（Hartmanis–Stearns 1965）：對任意可建構函數 \(t_2(n)\) ，存在語言可在 \(O(t_2(n))\) 時間內判定、但不能在 \(o(t_2(n)/\log t_2(n))\) 時間內判定。

一年後他們與 Philip Lewis 提出複雜性類的概念框架，並引入 Blum 公理（1967，Blum）使「複雜性」的定義機器無關。兩人因此獲 1993 年圖靈獎。本節的主題：對角線法如何從「不可判定」升級為「需要更多時間」。

時間可建構函數與複雜性類#

定義： \(t(n)\) 是時間可建構的，若映射 \(n \mapsto t(n)\) （一進位表示）可在 \(O(t(n))\) 時間內計算。多項式、 \(2^n\) 、 \(n \log n\) （近可建構）皆然。

定義： \(\mathrm{TIME}(t(n))\) = 可被圖靈機在 \(O(t(n))\) 時間內判定的語言之集合。 \(\mathrm{P} = \bigcup_k \mathrm{TIME}(n^k)\) 。

「多項式」作為可行性的分界線（Cobham 1965 獨立提出）基於兩個觀察：閉包性佳（多項式複合仍多項式），且對機器模型穩健——模擬開銷是多項式（1.2 節），所以 P 在所有合理模型上相同（機器無關性，Church-Turing 論題的複雜性版）。

對角線法的升級版#

證明思想與 4.1 節同源，但目標從「不可能」變成「不可能這麼快」：

  1. 枚舉所有圖靈機 \(M_1, M_2, \dots\) ；
  2. 對輸入 \(x\) （長度 \(n\) ），機器 \(D\) 在 \(O(t_2(n))\) 時間內模擬 \(M_i(x)\) 至 \(t_1(n) = o(t_2(n)/\log t_2(n))\) 步；
  3. 模擬完成： \(D\) 反轉答案（ \(M_i\) 接受則 \(D\) 拒絕）；未完成： \(D\) 自行決定一個預設答案。

\(D\) 的語言與每個 \(t_1(n)\) -時間機器在無窮多個輸入上不同 → 不屬於 \(\mathrm{TIME}(t_1)\) 。而 \(D\) 自己跑 \(O(t_2)\) 時間（對角線構造的及時性需要那個 \(\log t_2\) 因子——那是模擬開銷的代價）。

推論（重要階層）：

\[ \mathrm{P} \subsetneq \mathrm{EXPTIME} \subsetneq \mathrm{2\text{-}EXPTIME} \subsetneq \cdots \]

時間階層定理是迄今唯一能分離具體時間類別的技術。空間階層定理（Ibarra; Sipser）稍強： \(\mathrm{SPACE}(t) \subsetneq \mathrm{SPACE}(s)\) 對 \(t = o(s)\) 成立，故 \(\mathrm{PSPACE} \subsetneq \mathrm{EXPSPACE}\) ，且 \(\mathrm{P} \subseteq \mathrm{PSPACE}\) 中已知至少一端嚴格（ \(\mathrm{P} \subsetneq \mathrm{EXPSPACE}\) ）。

多帶機器與線性加速#

Hartmanis–Stearns 論文同時回答了模型問題： \(k\) 帶圖靈機比單帶最多快一個 \(O(n)\) 對數級因子（確切地：單帶模擬 \(k\) 帶 \(t\) 步需 \(O(t^2)\) ；隨後 Hennie–Stearns 1966 改進為 \(O(t \log t)\) ）。因此：

  • 複雜性類（多項式、多項式時間互換）對帶數不敏感——類的定義是穩健的；
  • 但精確的時間下界依賴模型——例如回文判定：單帶圖靈機需要 \(\Omega(n^2)\) （Myhill 的下界技術！2.3 節鴿籠法的前身），兩帶機只需 \(O(n \log n)\) 。這是「模型穩健性有極限」的教科書例子。

虛擬碼：對角線機 D 的及時實作#

def D(x):
    """時間階層的對角線機: O(t2(n)) 時間"""
    n = len(x)
    limit = t1(n)                       # t1(n) = t2(n) / log t2(n) 量級
    for i in range(1, small_enough(n)): # 只模擬「小號碼」的機器
        # 關鍵: 模擬 M_i(x) 需要 O(t1(n) * overhead(i))
        # overhead 與 i 相關 → 必須只對 i <= log t2(n) 範圍做
        # (這就是定理裡 log 因子的來源)
        r = simulate(M[i], x, steps=limit // overhead(i))
        if r == "accept":
            return "reject"             # 反轉 → 與 M_i 在 x 上不同
        if r == "reject":
            return "accept"
    return "reject"                     # 預設答案

「及時完成所有反轉」與「覆蓋夠多機器」之間的張力，正是 \(\log\) 因子與後續所有下界技術改良（delayed diagonalization、zap of functions）的研究主題。

時間階層定理給不了什麼：P vs NP 的牆#

注意定理的分離都是「超線性對數差距」： \(t_2 / (t_1 \log t_2) \to \infty\) 。它不能證明 \(\mathrm{P} \ne \mathrm{NP}\) （那需要分離 \(n^k\) 與 \(n^{k+1}\) 型的近差距），也不能分離 \(\mathrm{TIME}(n^2)\) 與 \(\mathrm{TIME}(n^3)\) 。更深的障礙：Baker–Gill–Solovay 相對化障礙（1975）——存在神諭 \(A\) 使 \(\mathrm{P}^A = \mathrm{NP}^A\) ，又存在 \(B\) 使 \(\mathrm{P}^B \ne \mathrm{NP}^B\) ；而對角線法自動相對化，故純對角線永遠解不了 P vs NP（詳見 5.3 節）。這說明 Hartmanis–Stearns 的技術有其內在極限——下界的證明需要「利用問題結構」的新數學。

歷史意義與後續發展#

  • 複雜性理論誕生：Hartmanis–Stearns 使「分類問題的固有難度」成為數學學科；Blum 公理（1967）把複雜性測度公理化，證明加速定理（任何函數存在無限多次「加速」的等價程式——程式的最優性本身不可判定！Rice 式幽靈再現）。
  • 演算法設計的座標系：P/NP/PSPACE/EXPTIME 的地圖（5.2 節）讓工程師說得出「這問題在座標系的哪裡」；階層定理保證地圖上確實有更高的山——總存在本質上更難的問題。
  • 密碼學的土壤：階層定理保證「單向函數候選」的邏輯空間（存在需要指數時間的問題，故「難以反轉」的假設有理論地基）；現代密碼學以複雜性假設為公理（5.3 節）。
  • 實務影響：SAT 求解器、混合整數規劃等「指數時間但實務可行」的工具崛起，推動了參數化複雜性（FPT）與平均情況複雜性（Levin）——複雜性理論自己也在回應工程界的反饋，持續細化「難」的定義。

重點整理#

  • Hartmanis–Stearns 1965：首創時間複雜性類；時間階層定理以「及時對角線」分離 \(\mathrm{TIME}(t_1) \subsetneq \mathrm{TIME}(t_2)\) 。
  • P、EXPTIME 等類對合理機器模型穩健（模擬開銷多項式/對數級）；但精確下界依賴模型（回文 \(n^2\) vs \(n\log n\) ）。
  • 對角線法無法分離近差距類，且自動相對化——P vs NP 需要新數學（5.3 節）。
  • 複雜性理論自此以「資源換能力」的階層觀點組織整個學科，為 NP 完全理論與密碼學鋪路。