時間階層定理（time hierarchy theorem）

複雜度理論中幾乎每個分離都是未解的猜想，但階層定理是難得、得來不易的例外，在這裡我們真的能「證明」更多資源換來更多能力。時間階層定理對步數這麼說：給機器真正更多的時間，它就能判定嚴格更多的語言。確實存在能在 n^3 時間內解、卻就是無法在 n^2 時間內解的問題，再聰明的技巧都填不平這道縫。它是保證時間階梯真的會往上爬的基石。

形式上（一個乾淨的版本），若 f 與 g 是表現良好（時間可構造）的函數，且 f 成長得比 g 夠快——具體說 g(n) 乘以 log g(n) 是 o(f(n))——則 TIME(f(n)) 嚴格包含 TIME(g(n))。證明是「帶時鐘的對角線論證」。建造一台機器 D，給定一台機器 M 的程式碼當輸入，就用一個計數器當碼錶，模擬 M 跑在它自己的程式碼上 f(n) 步；若 M 在預算內停機並接受，則 D 拒絕，否則 D 接受。於是 D 的語言在每台「在較小界限內執行的機器」自己的描述上，都與那台機器不同——這正是 Cantor 的對角線論證，如今加上了計時。那個小小的 log 因子是通用模擬追蹤時鐘的額外開銷。

回報是一連串真正的分離：例如 P 嚴格包含於 EXPTIME 是一條定理，而非猜想，因為指數時間多過任何單一多項式。所以確實存在可判定、卻可證明需要指數時間的問題，一道無窮的、愈來愈難的問題階梯。要保持誠實的提醒：這個定理分離的是相差超過一個對數因子的類別，所以它並不能解決鄰近的問題，如 P 對 NP（那些並非純粹「同一資源更多」的差距，它們牽涉非確定性）。它告訴我們階梯會往上爬，卻沒告訴我們兩種不同的階梯該如何比較。