ELEMENTARY

For other meanings, see Elementary.

In computational complexity theory, the complexity class $\mathsf{E}\mathsf{L}\mathsf{E}\mathsf{M}\mathsf{E}\mathsf{N}\mathsf{T}\mathsf{A}\mathsf{R}\mathsf{Y}$ consists of the decision problems that can be solved in time bounded by an elementary recursive function. The most quickly-growing elementary functions are obtained by iterating an exponential function such as $2^n$ for a bounded number $k$ of iterations, $$\begin{array}{c}{2}^{2^{2^{{\cdot }^{{\cdot }^{{\cdot }^n}}}}}\end{array}\}k.$$ Thus, $\mathsf{E}\mathsf{L}\mathsf{E}\mathsf{M}\mathsf{E}\mathsf{N}\mathsf{T}\mathsf{A}\mathsf{R}\mathsf{Y}$ is the union of the classes

$\begin{array}{rl}\mathsf{E}\mathsf{L}\mathsf{E}\mathsf{M}\mathsf{E}\mathsf{N}\mathsf{T}\mathsf{A}\mathsf{R}\mathsf{Y}& =\bigcup _{k\in \mathbb{\mathbb{N}}}k\text{-}\mathsf{E}\mathsf{X}\mathsf{P}\\ & =\mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}\left(2^n\right)\cup \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}\left(2^{2^n}\right)\cup \mathsf{D}\mathsf{T}\mathsf{I}\mathsf{M}\mathsf{E}\left(2^{2^{2^n}}\right)\cup \cdots .\end{array}$

It is sometimes described as iterated exponential time, though this term more commonly refers to time bounded by the tetration function. This complexity class can be characterized by a certain class of "iterated stack automata", pushdown automata that can store the entire state of a lower-order iterated stack automaton in each cell of their stack. These automata can compute every language in $\mathsf{E}\mathsf{L}\mathsf{E}\mathsf{M}\mathsf{E}\mathsf{N}\mathsf{T}\mathsf{A}\mathsf{R}\mathsf{Y}$, and cannot compute languages beyond this complexity class. The time hierarchy theorem implies that $\mathsf{E}\mathsf{L}\mathsf{E}\mathsf{M}\mathsf{E}\mathsf{N}\mathsf{T}\mathsf{A}\mathsf{R}\mathsf{Y}$ has no complete problems. Every elementary recursive function can be computed in a time bound of this form, and therefore every decision problem whose calculation uses only elementary recursive functions belongs to the complexity class $\mathsf{E}\mathsf{L}\mathsf{E}\mathsf{M}\mathsf{E}\mathsf{N}\mathsf{T}\mathsf{A}\mathsf{R}\mathsf{Y}$.