Jump to content

ELEMENTARY: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
m wrong link
this is unusual and confusing terminology
Line 17: Line 17:
\end{align}
\end{align}
</math>
</math>
and is also called '''iterated exponential time'''.<ref>{{citation|url=https://complexityzoo.net/Complexity_Zoo:E#elementary|title=ELEMENTARY|work=Complexity Zoo|access-date=2024-11-03}}</ref>
and is also sometimes called ''iterated exponential time'',<ref>{{citation|url=https://complexityzoo.net/Complexity_Zoo:E#elementary|title=ELEMENTARY|work=Complexity Zoo|access-date=2024-11-03}}</ref> though this more commonly refers to time bounded by the [[tetration]] function.


This complexity class can be characterized by a certain class of "iterated stack automata", [[pushdown automaton|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 <math>\mathsf{ELEMENTARY}</math>, and cannot compute languages beyond this complexity class.<ref>{{citation
This complexity class can be characterized by a certain class of "iterated stack automata", [[pushdown automaton|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 <math>\mathsf{ELEMENTARY}</math>, and cannot compute languages beyond this complexity class.<ref>{{citation

Revision as of 21:01, 5 November 2024

In computational complexity theory, the complexity class 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 for a bounded number of iterations,

Thus, is the union of the classes

and is also sometimes called iterated exponential time,[1] though this more commonly refers to time bounded by the tetration function.

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 , and cannot compute languages beyond this complexity class.[2] The complete problems for include determining whether two universal relational sentences in mathematical logic have the same largest models (where, for a model to be largest, it must be finite).[3]

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 .

References

  1. ^ "ELEMENTARY", Complexity Zoo, retrieved 2024-11-03
  2. ^ 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
  3. ^ 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, MR 1942515