在计算复杂度理论里面,复杂度类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。