ELEMENTARY
Encyclopedia
In computational complexity theory
, the complexity class
ELEMENTARY of elementary recursive functions is the union of the classes in the exponential hierarchy.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
ELEMENTARY of elementary recursive functions is the union of the classes in the exponential hierarchy.
-
The name was coined by László KalmárLászló KalmárLászló Kalmár was a Hungarian mathematician and Professor at the University of Szeged. Kalmár is considered the founder of mathematical logic and theoretical Computer Science in Hungary.- Biography :...
, in the context of recursive functionsComputable functionComputable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
and undecidabilityUndecidable problemIn computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARYNONELEMENTARYIn computational complexity theory, the complexity class NONELEMENTARY is the complement of the class ELEMENTARY.Example decidable problems in NONELEMENTARY this class are:* the problem of regular expression equivalence with not...
. Most notably, there are primitive recursive problems which are not in ELEMENTARY. We know
- LOWER-ELEMENTARY
EXPTIMEEXPTIMEIn computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
ELEMENTARY 
PRPR (complexity)PR is the complexity class of all primitive recursive functions – or, equivalently, the set of all formal languages that can be decided by such a function...
Whereas ELEMENTARY contains bounded applications of exponentiationExponentiationExponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
(for example,
), PRPR (complexity)PR is the complexity class of all primitive recursive functions – or, equivalently, the set of all formal languages that can be decided by such a function...
allows more general hyper operators (for example, tetrationTetrationIn mathematics, tetration is an iterated exponential and is the next hyper operator after exponentiation. The word tetration was coined by English mathematician Reuben Louis Goodstein from tetra- and iteration. Tetration is used for the notation of very large numbers...
) which are not contained in ELEMENTARY.
Definition
The definitions of elementary recursive functions are the same as for primitive recursive functionPrimitive recursive functionThe primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...
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.
- Subtraction function: f(x, y) = x - y if y < x, or 0 if y ≥ x. This function is used to define conditionals and iteration.
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:
is elementary recursive if g is elementary recursive. - Bounded product:
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.
Basis for ELEMENTARY
The class of elementary functions coincides with the closure with respect to composition of the projections and one of the following function sets:
, 
, 
, where 
is the subtraction function defined above.
Descriptive characterization
In descriptive complexityDescriptive complexityDescriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the...
, ELEMENTARY is equal to the class of high order queriesHO (complexity)High-order logic is an extension of first-order and second-order with high order quantifiers. In descriptive complexity we can see that it is equal to the ELEMENTARY functions...
. This means that every language in the ELEMENTARY complexity class can be written as a high order formula that is true only for the elements on the language. More precisely,
, where 
indicates a tower of 
exponentiations and 
is the class of queries that begin with existential quantifiers of 
th order and then a formula of 
th order.
See also
- Elementary function arithmetic
- Primitive recursive functionPrimitive recursive functionThe primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...
- Grzegorczyk hierarchyGrzegorczyk hierarchyThe Grzegorczyk hierarchy , named after the Polish logician Andrzej Grzegorczyk, is a hierarchy of functions used in computability theory . Every function in the Grzegorczyk hierarchy is a primitive recursive function, and every primitive recursive function appears in the hierarchy at some level...
- EXPTIMEEXPTIMEIn computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
- LOWER-ELEMENTARY