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:
“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)
“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)