Elementary recursive function

For other meanings, see Elementary function.

The term elementary was originally introduced by László Kalmár in the context of computability theory. He defined the class of elementary recursive functions ("Kalmár elementary functions") as a subset of the primitive recursive functions — specifically, those that can be computed using a limited set of operations such as composition, bounded sums, and bounded products. These functions grow no faster than a fixed-height tower of exponentiation (for example, $O(2^{2^{n}})$). Not all primitive recursive functions are elementary; for example, tetration grows too rapidly to be included in the elementary class. The elementary recursive functions correspond to the class ${\mathcal {E}}^{3}$ of the Grzegorczyk hierarchy.

In computational complexity theory, the term ELEMENTARY refers to a class of decision problems solvable in elementary time — that is, within time bounded by some fixed number of exponentials. Formally:

${\mathsf {ELEMENTARY}}=\bigcup _{k\in \mathbb {N} }{\text{DTIME}}(\exp ^{k}(n^{c}))$

where $\exp ^{k}(n)$ denotes a k-level exponential tower (e.g., $2^{2^{\cdot ^{\cdot ^{n}}}}$).

Although the name comes from the same historical origin, the ELEMENTARY complexity class deals with decision problems and Turing machine runtime, rather than total functions.