ELEMENTARY

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. The most quickly-growing elementary functions are obtained by iterating an exponential function such as $2^{n}$ for a bounded number $k$ of iterations, $\left.{\begin{matrix}2^{\scriptstyle 2^{\scriptstyle 2^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle \cdot ^{\scriptstyle n}}}}}}\end{matrix}}\right\}k.$

Thus, ${\mathsf {ELEMENTARY}}$ is the union of the classes

{\begin{aligned}{\mathsf {ELEMENTARY}}&=\bigcup _{k\in \mathbb {N} }k{\mathsf {{\mbox{-}}EXP}}\\&={\mathsf {DTIME}}\left(2^{n}\right)\cup {\mathsf {DTIME}}\left(2^{2^{n}}\right)\cup {\mathsf {DTIME}}\left(2^{2^{2^{n}}}\right)\cup \cdots .\end{aligned}}

It is sometimes described as iterated exponential time,^[1] though this term more commonly refers to time bounded by the tetration function.^[2]

This complexity class can be characterized by a certain class of "iterated stack automata", pushdown automata that can store the entire state of a lower-order iterated stack automaton in each cell of their stack. These automata can compute every language in ${\mathsf {ELEMENTARY}}$ , and cannot compute languages beyond this complexity class.^[3] The time hierarchy theorem implies that ${\mathsf {ELEMENTARY}}$ has no complete problems.

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}}$ .

References

^ "ELEMENTARY", Complexity Zoo, retrieved 2024-11-03
^ Friedman, Harvey (1999), "Some decision problems of enormous complexity" (PDF), 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999, {IEEE} Computer Society, pp. 2–12, doi:10.1109/LICS.1999.782577, ISBN 0-7695-0158-3, MR 1942515
^ Engelfriet, Joost (1991), "Iterated stack automata and complexity classes", Information and Computation, 95 (1): 21–75, doi:10.1016/0890-5401(91)90015-T, MR 1133778

[1] "ELEMENTARY", Complexity Zoo, retrieved 2024-11-03

[2] Friedman, Harvey (1999), "Some decision problems of enormous complexity" (PDF), 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999, {IEEE} Computer Society, pp. 2–12, doi:10.1109/LICS.1999.782577, ISBN 0-7695-0158-3, MR 1942515

[3] Engelfriet, Joost (1991), "Iterated stack automata and complexity classes", Information and Computation, 95 (1): 21–75, doi:10.1016/0890-5401(91)90015-T, MR 1133778

[1]

[2]

[3]

Complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL FL NL NL-complete NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete TFNP FNP AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system
List of complexity classes

Fahrer / Team für die Suche eingeben:

Fahrer / Team für die Suche eingeben:

Langbahn Team – Weltmeisterschaft

ELEMENTARY

References