ELEMENTARY

この項目では、複雑性クラスについて説明しています。Linuxディストリビューションについては「elementary OS」をご覧ください。

計算複雑性理論において 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}}}$

クラス ELEMENTARY に属す関数は初等帰納的（しょとうきのうてき、英: elementary recursive）あるいは単に初等的と呼ばれる。この名称はカルマール（英語版）による造語である。

帰納的関数や決定不能性の文脈で扱われる多くの問題は ELEMENTARY よりも高いレベルにある。いくつかの帰納的問題は ELEMENTARY を超える。すなわち NONELEMENTARY となる。とくに注目されるのは、原始帰納的問題で ELEMENTARY に属さないものが存在することである。次が知られている。

LOWER-ELEMENTARY ${\displaystyle \subsetneq }$ EXPTIME ${\displaystyle \subsetneq }$ ELEMENTARY ${\displaystyle \subsetneq }$ PR ${\displaystyle \subsetneq }$ R

ELEMENTARY は指数関数の定数回の入れ子（例えば ${\displaystyle 2^{2^{n}}}$）を含むが、PRは指数関数の一般化であるハイパー演算子で ELEMENTARY に属さないもの（例えばテトレーション）を含む。