この項目では、複雑性クラスについて説明しています。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 }
性質

初等的関数は限定原始再帰で閉じている。すなわち g, h と j が初等的であり f ( t , u ¯ ) ≤ j ( t , u ¯ ) {\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})} f ( 0 , u ¯ ) = g ( u ¯ ) {\displaystyle f(0,{\bar {u}})=g({\bar {u}})} f ( t + 1 , u ¯ ) = h ( t , u ¯ , f ( t , u ¯ ) ) {\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}

ならば、 f もまた初等的である。

初等的関数は次の何れかの関数で支配される。すなわち任意の初等的関数は次に挙げる関数の何れかより小さい： x , 2 x , 2 2 x , 2 2 2 x , … {\displaystyle x,2^{x},2^{2^{x}},2^{2^{2^{x}}},\ldots }

このリストを枚挙する原始帰納的関数 f ( c , x ) = 2 2 ⋅ ⋅ x ⏟ c {\displaystyle f(c,x)=\underbrace {2^{2^{\cdot ^{\cdot ^{x}}}}} _{c}} は初等的でない：対角線論法による。 f ( c , x ) {\displaystyle f(c,x)} が初等的と仮定する。すると f ( x , x ) {\displaystyle f(x,x)} もまた初等的であるから、ある c に対して f ( x , x ) < f ( c , x ) {\displaystyle f(x,x)<f(c,x)} が成り立つ。ところがここで x = c {\displaystyle x=c} とすると不合理を得る。同様の増大度を持つテトレーションもまた初等的でない原始帰納的関数である。

クラス ELEMENTARY はレベル3のグジェゴルチク階層、深さ2のループプログラムで計算可能な関数のクラス、時間計算量が指数関数の定数回の反復で抑えられる関数のクラスなどと一致する。
低初等帰納的関数

限定積を用いずに定義できる初等的関数は低初等帰納的（英: lower elementary recursive）という。