在計算複雜性理論內,指數譜系是一個複雜度類的分類層級(hierarchy),以EXPTIME開始:
![{\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{n^{k}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/836b0b0b75283d524327f44bcb78b276c17452bc)
然後接著
![{\displaystyle {\mbox{2-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{n^{k}}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a044d8604e31a06055c2732b442dbe04e6418dd0)
![{\displaystyle {\mbox{3-EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{DTIME}}\left(2^{2^{2^{n^{k}}}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a46fac9205eeae911175e9936ccdb6db4a2f5978)
,以下雷同。
我們已知P ⊂ EXPTIME ⊂ 2-EXPTIME ⊂ 3-EXPTIME ⊂ …。跟相類似的多項式譜系不同,時間譜系理論(Time hierarchy theorem)保證了這列關係都是真子集(proper),意思是,存在語言在EXPTIME而不在P內,也存在語言在2-EXPTIME但不在EXPTIME內,以下類推。
將所有指數譜系的複雜度類作聯集,我們會得到一個大的複雜度類,名為ELEMENTARY。
參考資料[编辑]
- Computational Complexity. Addison Wesley, 1994. (pp 497-498)
|
---|
| 易解复杂度类 | | |
---|
| 怀疑难解复杂度类 | |
---|
| 难解复杂度类 | |
---|
| 复杂度类的谱系 | |
---|
| 相关复杂度族 | |
---|
|