在計算複雜度理論裡面,複雜度類ELEMENTARY是所有指數譜系裡面的複雜度類聯集:
![{\displaystyle {\begin{matrix}\mathrm {ELEMENTARY} &=&\mathrm {EXP} \cup \mathrm {2EXP} \cup \mathrm {3EXP} \cup \cdots \\&=&\mathrm {DTIME} (2^{n})\cup \mathrm {DTIME} (2^{2^{n}})\cup \mathrm {DTIME} (2^{2^{2^{n}}})\cup \cdots \end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1fcdc586d7b5aa2e0e2c6977419cf74488c4eae1)
這名稱最早是為了探討可計算函數和不可判定問題,由László Kalmár所提出;most problems in it are far from elementary。Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY。相當值得注意的,有一些原始遞歸函數問題不在ELEMENTARY內。我們已知:
LOWER-ELEMENTARY
EXPTIME
ELEMENTARY
PR
與ELEMENTARY僅包含有限的冪(例如,
)比較,PR使用的 超運算更一般化(例如,tetration),因此PR不包含於ELEMENTARY。
|
---|
| 易解复杂度类 | | |
---|
| 怀疑难解复杂度类 | |
---|
| 难解复杂度类 | |
---|
| 复杂度类的谱系 | |
---|
| 相关复杂度族 | |
---|
|