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

計算複雑性理論において ELEMENTARY とは指数階層（英語版）の和集合で表される複雑性クラスである。 E L E M E N T A R Y = E X P ∪ 2 E X P ∪ 3 E X P ∪ ⋯ = D T I M E ( 2 n ) ∪ D T I M E ( 2 2 n ) ∪ D T I M E ( 2 2 2 n ) ∪ ⋯ {\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 は指数関数の定数回の入れ子（例えば 2 2 n {\displaystyle 2^{2^{n}}} ）を含むが、PRは指数関数の一般化であるハイパー演算子で ELEMENTARY に属さないもの（例えばテトレーション）を含む。
定義と例

初等帰納的関数の定義は原始帰納を限定和と限定積に置き換わっている点を除けば原始帰納的関数と同様に定義される。（通常、減算は原始帰納的関数の基本関数に含めないが、原始帰納的である。）全ての関数は自然数に対して作用するものとする。基本関数は次のものからなる：
ゼロ関数： Z ( x → ) = 0 {\displaystyle Z({\overrightarrow {x}})=0}

後者関数： S ( x ) = x + 1 {\displaystyle S(x)=x+1}

射影関数: P μ ν ( x → ) = x μ {\displaystyle P_{\mu }^{\nu }({\overrightarrow {x}})=x_{\mu }}

減算関数: x − ˙ y = { x − y if  x ≥ y 0 otherwise {\displaystyle x{\dot {-}}y={\begin{cases}x-y&{\mbox{if }}x\geq y\\0&{\mbox{otherwise}}\end{cases}}}

これらの基本関数に次の基本構成を繰り返して得られる関数が初等帰納的関数である：
合成: h ( x → ) = f ( g 1 ( x → ) , g 2 ( x → ) , … , g μ ( x → ) ) {\displaystyle h({\overrightarrow {x}})=f(g_{1}({\overrightarrow {x}}),g_{2}({\overrightarrow {x}}),\ldots ,g_{\mu }({\overrightarrow {x}}))}

限定和: f ( x → , y ) = ∑ z < y g ( x → , z ) {\displaystyle f({\overrightarrow {x}},y)=\sum \limits _{z<y}g({\overrightarrow {x}},z)}

限定積: f ( x → , y ) = ∏ z < y g ( x → , z ) {\displaystyle f({\overrightarrow {x}},y)=\prod \limits _{z<y}g({\overrightarrow {x}},z)}

初等的関数の例としては次のものがある：乗算関数： x ⋅ y = ∑ z < y x {\displaystyle x\cdot y=\sum \limits _{z<y}x} 加算関数： x + y = S ( x ) ⋅ S ( y ) − ˙ S ( x ⋅ y ) {\displaystyle x+y=S(x)\cdot S(y){\dot {-}}S(x\cdot y)} 冪乗関数： x y = ∏ z < y x {\displaystyle x^{y}=\prod \limits _{z<y}x} 素数列： p n = 2 , 3 , 5 , 7 , 11 , … {\displaystyle p_{n}=2,3,5,7,11,\ldots }