ELEMENTARY

For other meanings, see Elementary.

In computational complexity theory, the complexity class ${\displaystyle {\mathsf {ELEMENTARY}}}$ consists of the decision problems that can be solved in time bounded by an elementary function. The most quickly-growing elementary functions are obtained by iterating an exponential function such as ${\displaystyle 2^{n}}$ for a bounded number ${\displaystyle k}$ of iterations, $${\displaystyle \left.{\begin{matrix}2^{\scriptstyle 2^{\scriptstyle 2^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle n}}}}}}\end{matrix}}\right\}k}$$

Thus, it is the union of the classes

${\displaystyle {\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots \end{aligned}}}$

and is also called iterated exponential time.^[1]

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 ${\displaystyle {\mathsf {ELEMENTARY}}}$, and cannot compute languages beyond this complexity class.^[2] The complete problems for ${\displaystyle {\mathsf {ELEMENTARY}}}$ include determining whether two universal relational sentences in mathematical logic have the same largest models (where, for a model to be largest, it must be finite).^[3]

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 ${\displaystyle {\mathsf {ELEMENTARY}}}$.

References

1. "ELEMENTARY", Complexity Zoo, retrieved 2024-11-03
2. Engelfriet, Joost (1991), "Iterated stack automata and complexity classes", Information and Computation, 95 (1): 21–75, doi:10.1016/0890-5401(91)90015-T, MR 1133778
3. Friedman, Harvey (1999), "Some decision problems of enormous complexity" (PDF), 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999, {IEEE} Computer Society, pp. 2–12, doi:10.1109/LICS.1999.782577, MR 1942515