1993 Juris Hartmanis & Richard Stearns —— 幫計算的「時間」立法#

「機器能解的問題之外，還有一個更大的問題：多快能解？ 1965 年，兩人用一篇論文把『時間』變成可以分級的數學對象。」

案件檔案#

項目	內容
得主	Juris Hartmanis (1928–2022)、Richard E. Stearns (1936–)
得獎理由	計算複雜度理論的奠基：時間複雜度與分級定理
關鍵詞	時間分級定理、多帶圖靈機、複雜度類

Turing（λ演算史 1936 案）定義了「可計算」，但只分「能/不能」。實務中 IBM 主機上兩個可計算問題的體感天差地遠。謎題： 「難度」能否成為嚴格數學？ Cook（1982 案）的 NP 理論正是站在本案地基上。

DTIME(T(n))：確定性圖靈機在 O(T(n)) 時間內可解的語言類
以「多帶圖靈機」為標準模型（帶數不影響多項式等級）

首次把資源（時間/空間）納入定義，計算理論從「是否可解」升級為「以何代價可解」。

若 t₂(n) log t₂(n) = o(t₁(n))，則
  DTIME(t₂(n)) ⊊ DTIME(t₁(n))
即：給夠多時間，機器必然能解更多問題

證明手法是對角化的精細版：構造一個在 t₁ 時間內模擬所有 t₂ 時間機器並「唱反調」的機器（log 因子來自模擬開銷）。「更強的資源 = 嚴格更大的能力」自此有了定理。

同一論文證明線性加速定理：任何常數倍加速皆可達（預先壓縮帶內容）——但多項式與指數之間的鴻溝無法靠工程技巧消除。「多項式時間」成為可行性的正式定義，理由在此：它對模型選擇、常數因子不變（機器無關性， machine independence）。

Hartmanis 亦奠基空間複雜度與「isomorphism conjecture」（所有 NP 完全問題在多項式同構意義下是同一個問題—— 待解至今）。Savitch 定理（NSPACE(s) ⊆ DSPACE(s²)）緊隨其後，補全空間分級。

本案與 Cook/Karp 案的分工：

案件	問的問題	工具
Hartmanis–Stearns	類與類之間是否嚴格分離	對角化
Cook–Karp	哪些問題是「最難的」	歸約

兩者合璧才有今日的複雜度地圖（P、NP、PSPACE、EXPTIME…… 與已證的包含鏈 P ⊊ EXPTIME 等）。