In computational complexity theory, the complexity class ELEMENTARY is the union of the classes in the exponential hierarchy.

$\backslash begin\{matrix\}$

\rm{ELEMENTARY} & = & \rm{EXP}\cup\rm{2EXP}\cup\rm{3EXP}\cup\cdots \\ & = & \rm{DTIME}(2^{n})\cup\rm{DTIME}(2^{2^{n}})\cup \rm{DTIME}(2^{2^{2^{n}}})\cup\cdots \end{matrix}

The name was coined in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY.

Complexity classes