consists of the decision problems that can be solved in time bounded by an elementary recursive function.
is the union of the classes It is sometimes described as iterated exponential time,[1] 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.
[3] The time hierarchy theorem implies that
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