Elementary recursive

In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes

The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know

Whereas ELEMENTARY contains bounded applications of exponentiation (for example, ${\displaystyle O(2^{2^{n}})}$), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY.

The definitions of elementary recursive functions are the same as for primitive recursive functions, except that primitive recursion is replaced by bounded summation and bounded product. All functions work over the natural numbers. The basic functions, all of them elementary recursive, are:

From these basic functions, we can build other elementary recursive functions.

The class of elementary functions coincides with the closure with respect to composition of the projections and one of the following function sets: ${\displaystyle \{n+1,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,n^{m}\}}$, ${\displaystyle \{n+m,n\,{\stackrel {.}{-}}\,m,\lfloor n/m\rfloor ,2^{n}\}}$, ${\displaystyle \{n+m,n^{2},n\,{\bmod {\,}}m,2^{n}\}}$, where ${\displaystyle n\,{\stackrel {.}{-}}\,m=\max\{n-m,0\}}$ is the subtraction function defined above.

...
Wikipedia