ELEMENTARY

From Free net encyclopedia

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

<math> \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}

</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, and are thus NONELEMENTARY.

Image:E-to-the-i-pi.svg This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://www.netipedia.com/index.php/ELEMENTARY"