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} The name was coined by Laszlo Kalmar, in the context of recursive functions and undecidability; most problems in it are far from elementary.

PropertyValue
dbpprop:abstract
  • 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} The name was coined by Laszlo Kalmar, 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 EXPTIME <math>\subsetneq ELEMENTARY <math>\subsetneq PR Whereas ELEMENTARY contains bounded applications of exponentiation (for example, <math>\rm{O}), PR allows more general hyper operators (for example, <math>\rm{O}, using Knuth's up-arrow notation) which are not contained in ELEMENTARY.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • 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} The name was coined by Laszlo Kalmar, in the context of recursive functions and undecidability; most problems in it are far from elementary.
rdfs:label
  • ELEMENTARY
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of