In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes in the exponential hierarchy.
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)
“As if paralyzed by the national fear of ideas, the democratic distrust of whatever strikes beneath the prevailing platitudes, it evades all resolute and honest dealing with what, after all, must be every healthy literature’s elementary materials.”
—H.L. (Henry Lewis)
“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)