指數譜系

在計算複雜性理論內，指數譜系是一個複雜度類的分類層級(hierarchy)，以EXPTIME開始：

${\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right)}$

然後接著

${\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{k}}}\right)}$

${\displaystyle {\mbox{3-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{2^{n^{k}}}}\right)}$

，以下雷同。

我們已知P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …。跟相類似的多項式譜系不同，時間譜系理論(Time hierarchy theorem)保證了這列關係都是真子集(proper)，意思是，存在語言在EXPTIME而不在P內，也存在語言在2-EXPTIME但不在EXPTIME內，以下類推。

將所有指數譜系的複雜度類作聯集，我們會得到一個大的複雜度類，名為ELEMENTARY。

參考資料

• Computational Complexity. Addison Wesley, 1994. (pp 497-498)