ELEMENTARY

Template:About In computational complexity theory, the complexity class $𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸$ 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, $𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸$ is the union of the classes

$\begin{array}{cc}𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸& =\bigcup _{k\in \mathbb{N}}k\text{-}𝖤𝖷𝖯\\ & =𝖣𝖳𝖨𝖬𝖤\left(2^n\right)\cup 𝖣𝖳𝖨𝖬𝖤\left(2^{2^n}\right)\cup 𝖣𝖳𝖨𝖬𝖤\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 $𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸$, and cannot compute languages beyond this complexity class. The time hierarchy theorem implies that $𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸$ 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 $𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸$.