指數譜系

维基百科,自由的百科全书
跳转至: 导航搜索

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

\rm{EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{n^k}\right)

然後接著

\mbox{2-EXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{DTIME}\left(2^{2^{n^k}}\right)
\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)