ELEMENTARY

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

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

The name was coined by László Kalmár, 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. Most notably, there are primitive recursive problems which are not in ELEMENTARY. We know

LOWER-ELEMENTARY EXPTIME ELEMENTARY PR R

Whereas ELEMENTARY contains bounded applications of exponentiation (for example, ), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY.

Read more about ELEMENTARY:  Definition, Lower Elementary Recursive Functions, Basis For ELEMENTARY, Descriptive Characterization

Famous quotes containing the word elementary:

If men as individuals surrender to the call of their elementary instincts, avoiding pain and seeking satisfaction only for their own selves, the result for them all taken together must be a state of insecurity, of fear, and of promiscuous misery.
Albert Einstein (1879–1955)

Listen. We converse as we live—by repeating, by combining and recombining a few elements over and over again just as nature does when of elementary particles it builds a world.
William Gass (b. 1924)

When the Devil quotes Scriptures, it’s not, really, to deceive, but simply that the masses are so ignorant of theology that somebody has to teach them the elementary texts before he can seduce them.
Paul Goodman (1911–1972)