ELEMENTARY explained

ELEMENTARY 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,$$\backslash left.\backslash begin2^\backslash end\backslash right\backslash \}\; k.$$

Thus,

ELEMENTARY is the union of the classes\begin{align} ELEMENTARY & = c up _{k} k - EXP \\ & = DTIME \left( 2 ^{n\right)\cupDTIME\left(2} ^{2 ^{n}} \right)\cup DTIME \left( 2 ^{2 ^{2 ^{n}}} \right)\cup … . \end{align} 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

ELEMENTARY , and cannot compute languages beyond this complexity class. The time hierarchy theorem implies that ELEMENTARY 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

ELEMENTARY