ELEMENTARY

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

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^[2]

LOWER-ELEMENTARY ⊊ EXPTIME ⊊ ELEMENTARY ⊊ PR ⊊ R

Referències