EXPTIME（指數時間）

EXPTIME 是真正耗時的問題居住之處：那些能在指數步數內解出的問題，如某常數 k 的 2^(n^k)。想像一個問題，其解需要探索一棵每多一個輸入位元就規模加倍的可能性樹。對小輸入還好，但執行時間爆炸得如此之快，連中等大小的輸入在任何真實電腦上都變得無望。EXPTIME 是這種爆炸的形式家園，是從多項式時間往上一大跳的類別。

形式上，EXPTIME 是所有常數 k 的 TIME(2^(n^k)) 之聯集：能被一台確定型圖靈機在「2 的多項式次方」時間界限內判定的語言。它在地圖上的位置在一端是穩固的：P 包含於 NP 包含於 PSPACE 包含於 EXPTIME。最後一個包含成立，是因為一台多項式空間機器至多有 2^(多項式) 個相異格局，而若它從不重複某個格局（否則就永遠迴圈、從不判定），就必在那個指數數量的步數內停機。所以有界的空間強制了有界的時間，只是量呈指數地更大。

EXPTIME 的特別之處在於我們能「證明」它嚴格大於 P。由時間階層定理，P 嚴格包含於 EXPTIME，這是我們擁有的極少數無條件分離之一。所以確實存在可判定的問題——如以最佳對弈判定某些廣義棋盤遊戲（n 乘 n 西洋棋、跳棋）——可證明需要指數時間，無論演算法多聰明都永遠無法在多項式時間內解出。要釐清的提醒：P 嚴格在 EXPTIME 之內並「不」解決 P 對 NP 或 P 對 PSPACE；那些類別被夾在 P 與 EXPTIME 之間，而我們尚無法證明任何中間的包含是嚴格的。EXPTIME 只是離 P 夠遠，遠到階層定理終於咬得動。