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. Most notably, there are primitive recursive problems which are not in ELEMENTARY. We know
- LOWER-ELEMENTARY <math>\subsetneq</math> EXPTIME <math>\subsetneq</math> ELEMENTARY <math>\subsetneq</math> PR
Whereas ELEMENTARY contains bounded applications of exponentiation (for example, <math>\rm{O}(2^{2^n})</math>), PR allows more general hyper operators (for example, <math>\rm{O}(n\uparrow\uparrow n)</math>, using Knuth's up-arrow notation) which are not contained in ELEMENTARY.
Contents |
Definition
The definitions of elementary recursive functions are the same as for primitive recursive functions, 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. E.g., f() = 0.
- Successor function. E.g., 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(x1, ..., xn) = h(g1(x1, ..., xn), ..., gm(x1, ..., xn)) is elementary recursive if h is elementary recursive and each gi is elementary recursive.
- Bounded summation: <math>f(m, x_1, \ldots, x_n) = \sum\limits_{i=0}^mg(i, x_1, \ldots, x_n)</math> is elementary recursive if g is elementary recursive.
- Bounded product: <math>f(m, x_1, \ldots, x_n) = \prod\limits_{i=0}^mg(i, x_1, \ldots, x_n)</math> 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 functions 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 under composition. In particular, <math>x+y</math>, <math>[x/y]</math>, <math>\phi(x,y)</math>, <math>2^x</math> are sufficient, where <math>\phi</math> is defined as the function that returns the least place in the base x expansion of y where there is a digit 0.
See also
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
