查看“︁指數譜系”︁的源代码

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

:<math>\mbox{EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{n^k}\right)</math>

然後接著

:<math>\mbox{2-EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{2^{n^k}}\right)</math>
:<math>\mbox{3-EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{2^{2^{n^k}}}\right)</math>

，以下雷同。

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

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

== 參考資料 ==
{{Reflist}}
* ''Computational Complexity''. Addison Wesley, 1994. (pp 497-498)

{{-}}
{{複雜度類}}

[[Category:複雜度類]]