ELEMENTARY

En teoria de la complexitat, la classe de complexitat ELEMENTARY de les funcions recursives primitives és la unió de les classes

$\begin{array}{cc}\mathrm{E}\mathrm{L}\mathrm{E}\mathrm{M}\mathrm{E}\mathrm{N}\mathrm{T}\mathrm{A}\mathrm{R}\mathrm{Y}& =\mathrm{E}\mathrm{X}\mathrm{P}\cup \mathrm{2}\mathrm{E}\mathrm{X}\mathrm{P}\cup \mathrm{3}\mathrm{E}\mathrm{X}\mathrm{P}\cup \cdots \\ & =\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^n)\cup \mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{2^n})\cup \mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(2^{2^{2^n}})\cup \cdots \end{array}$

El nom va ser proposat per László Kalmár, en el context de funcions recursives i indecibilitat. Alguns problemes recursius cauen fora de la classe ELEMENTARY i, per tant, son dins de NO-ELEMENTARY. Particularment, hi ha problemes a les classes associades a la recursió primitiva que no està a ELEMENTARY.

Se sap que

LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R