ELEMENTARY
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computational complexity theory, the complexity class \mathsf{ELEMENTARY} consists of the decision problems that can be solved in time bounded by an elementary recursive function. Equivalently, these are the problems that can be solved in time bounded by an iterated exponential function with a bounded number of iterations. Every elementary recursive function can be computed in a time bound of this form, and therefore every decision problem whose calculation uses only elementary recursive functions belongs to the complexity class \mathsf{ELEMENTARY} . The time hierarchy theorem implies that \mathsf{ELEMENTARY} has no complete problems. Problems outside of \mathsf{ELEMENTARY} are the nonelementary problems.
Elementary may refer to:
Arts, entertainment, and media
Music
Elementary (Cindy Morgan album), 2001 Elementary (The End album), 2007 Elementary, a Melvin "Wah-Wah Watson" Ragin album, 1977
Other uses in arts, entertainment, and media
Elementary (TV series), a 2012 American drama television series "Elementary, my dear Watson", a catchphrase of Sherlock Holmes
Education
Elementary and Secondary Education Act, US Elementary education, or primary education, the first years of formal, structured education Elementary Education Act 1870, England and Wales Elementary school, a school providing elementary or primary education
Science and technology
ELEMENTARY, a class of objects in computational complexity theory Elementary, a widget set based on the Enlightenment Foundation Libraries Elementary abelian group, an abelian group in which every nontrivial element is of prime order Elementary algebra Elementary arithmetic Elementary charge, e, of a single electron Elementary definition, in mathematical logic elementary OS, a Linux distribution Elementary particle, in particle physics Elementary proof Elementary function
See also
Element (disambiguation) Elemental (disambiguation)
Text derived from https://en.wikipedia.org/w/index.php?oldid=1371839387 under CC BY-SA 4.0; modifications have been made.