- ELEMENTARY
In

computational complexity theory , thecomplexity class **ELEMENTARY**is the union of the classes in theexponential hierarchy .: $egin\{matrix\}\; m\{ELEMENTARY\}\; =\; m\{EXP\}cup\; m\{2EXP\}cup\; m\{3EXP\}cupcdots\; \backslash \; =\; m\{DTIME\}(2^\{n\})cup\; m\{DTIME\}(2^\{2^\{n)cup\; m\{DTIME\}(2^\{2^\{2^\{n\})cupcdots\; end\{matrix\}$

The name was coined by

Laszlo Kalmar , in the context ofrecursive function s andundecidability ; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thusNONELEMENTARY . Most notably, there areprimitive recursive problems which are not in ELEMENTARY. We know:LOWER-ELEMENTARY $subsetneq$

EXPTIME $subsetneq$ ELEMENTARY $subsetneq$ PRWhereas ELEMENTARY contains bounded applications of

exponentiation (for example, $m\{O\}(2^\{2^n\})$), PR allows more generalhyper operator s (for example, $m\{O\}(nuparrowuparrow\; n)$, usingKnuth's up-arrow notation ) which are not contained in ELEMENTARY.**Definition**The definitions of elementary recursive functions are the same as for

primitive recursive function s, except that primitive recursion is replaced by bounded summation and bounded product. All functions work over the natural numbers. The basic functions, all of them elementary recursive, are:#

**Zero function**. Returns zero: "f"(x) = 0.

#**Successor function**: "f"("x") = "x" + 1. Often this is denoted by "S", as in "S"("x"). Via repeated application of a successor function, one can achieve addition.

#**Projection functions**: these are used for ignoring arguments. For example, "f"("a", "b") = "a" is a projection function.From these basic functions, we can build other elementary recursive functions.

#

**Composition**: applying values from some elementary recursive function as an argument to another elementary recursive function. In "f"("x"_{1}, ..., "x"_{n}) = "h"("g"_{1}("x"_{1}, ..., "x"_{n}), ..., "g"_{m}("x"_{1}, ..., "x"_{n})) is elementary recursive if "h" is elementary recursive and each "g"_{i}is elementary recursive.

#**Bounded summation**: $f(m,\; x\_1,\; ldots,\; x\_n)\; =\; sumlimits\_\{i=0\}^mg(i,\; x\_1,\; ldots,\; x\_n)$ is elementary recursive if "g" is elementary recursive.

#**Bounded product**: $f(m,\; x\_1,\; ldots,\; x\_n)\; =\; prodlimits\_\{i=0\}^mg(i,\; x\_1,\; ldots,\; x\_n)$ is elementary recursive if "g" is elementary recursive.**Lower elementary recursive functions**"Lower elementary recursive" functions follow the definitions as above, except that bounded product is disallowed. That is, a lower elementary recursive function must be a zero, successor, or projection function, a composition of other lower elementary recursive functions, or the bounded sum of another lower elementary recursive function.

Whereas elementary recursive functions have potentially exponential growth, and comprise the

exponential hierarchy , the lower elementary recursive functions have polynomial growth.**Relationship to primitive recursion**The definitions for elementary recursive functions and

primitive recursive function s are identical, except that in lieu of primitive recursion, elementary recursion offers bounded sums and products. Bounded sums and products offer a more restricted means of repeatedly applying some function, and indeed the elementary recursive functions form a strict subset of the primitive recursive functions.**Basis for ELEMENTARY**J.P. Jones showed in 1988 that there is a 4-member set of

**ELEMENTARY**that generates it undercomposition. In particular,$x+y$, $[x/y]$, $phi(x,y)$, $2^x$ are sufficient, where $phi$ is defined asthe function that returns the least place in the base x expansion of y where there is a digit 0.**See also***

Primitive recursive function

*Grzegorczyk hierarchy

*EXPTIME **References*** Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3

* Jones, J.P., "Basis for the Kalmar Elementary Functions", Number Theory and Applications, ISBN 0-7923-0149-8

*Wikimedia Foundation.
2010.*

**Synonyms**:

### Look at other dictionaries:

**Elementary**— ist ein im Jahre 2007 entstandenes freies Software Projekt. Ursprünglich war es eine Sammlung von Programmen und Designs für Ubuntu, jetzt verfügt es über seine eigene Linux Distribution welche den Namen elementary OS trägt. Die erste Version,… … Deutsch Wikipedia**elementary OS**— … Википедия**Elementary**— Elementary: *Education ** Elementary education, consists of the first years of formal, structured education that occur during childhood. **Elementary school, a school providing elementary or primary education. Historically, a school in the UK… … Wikipedia**elementary**— elementary, elemental are often confused. Something is elementary which pertains to rudiments or beginnings; something is elemental which pertains to the elements, especially to the ultimate and basic constituents or forces {an elementary… … New Dictionary of Synonyms**Elementary**— Elementary … Википедия**Elementary**— El e*men ta*ry, a. [L. elementarius: cf. F. [ e]l[ e]mentaire.] 1. Having only one principle or constituent part; consisting of a single element; simple; uncompounded; as, an elementary substance. [1913 Webster] 2. Pertaining to, or treating of,… … The Collaborative International Dictionary of English**elementary**— I adjective abecedarian, apparent, basal, basic, beginning, crude, easy, easy to understand, elemental, foundational, fundamental, inceptive, initiatory, introductory, obvious, plain, precursory, prefatory, primary, primitive, primus, proemial,… … Law dictionary**elementary**— late 14c., having the nature of one of the four elements, from M.Fr. elementaire and directly from L. elementarius, from elementum (see ELEMENT (Cf. element)). Meaning rudimentary is from 1540s; meaning вЂњsimpleвЂќ is from 1620s. Elementary… … Etymology dictionary**elementary**— [el΄ə ment′ə rē, el΄əmen′trē] adj. [ME elementare < L elementarius] 1. ELEMENTAL 2. a) of first principles, rudiments, or fundamentals; introductory; basic; simple b) of or having to do with the formal instruction of children in basic subjects … English World dictionary**elementary**— [adj] simple, basic ABCs, abecedarian, basal, beginning, child’s play*, clear, duck soup*, easy, elemental, essential, facile, foundational, fundamental, initial, introductory, meat and potatoes*, original, plain, prefatory, preliminary, primary … New thesaurus**elementary**— ► ADJECTIVE 1) relating to the most rudimentary aspects of a subject. 2) straightforward and uncomplicated. 3) not decomposable into elements or other primary constituents. DERIVATIVES elementarily adverb … English terms dictionary