ELEMENTARY
|
|
In computational complexity theory, the complexity class ELEMENTARY is the union of the classes in the exponential hierarchy.
- <math>\rm{ELEMENTARY}=\rm{DTIME}(2^{n})\cup\rm{DTIME}(2^{2^{n}})\cup\rm{DTIME}(2^{2^{2^{n}}})\cup\cdots<math>
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, for example the problem of regular expression equivalence with not.