ELEMENTARY

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 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 𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸 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 𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸.

The time hierarchy theorem implies that 𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸 has no complete problems. Problems outside of 𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸 are the nonelementary problems.

Definition

edit edit source

The most quickly-growing elementary recursive functions are obtained by iterating an exponential function such as 2n for a bounded number k of iterations, 222⋅⋅⋅n}k times.

Thus, 𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸 is the union of the classes

𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸=⋃k∈ℕk-𝖤𝖷𝖯=𝖣𝖳𝖨𝖬𝖤(2n)∪𝖣𝖳𝖨𝖬𝖤(22n)∪𝖣𝖳𝖨𝖬𝖤(222n)∪⋯. It is sometimes described as iterated exponential time,[1] though this term more commonly refers to time bounded by the tetration function.[2]

Characterizations

edit edit source

Iterated stack automata

edit edit source

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.[3]

Higher-order logic

edit edit source

In descriptive complexity theory, ELEMENTARY is equal to the class HO of languages that can be described by a formula of higher-order logic. This means that every language in the ELEMENTARY complexity class corresponds to as a higher-order formula that is true for, and only for, the elements on the language. More precisely, 𝖭𝖳𝖨𝖬𝖤(22⋯2O(n))=∃𝖧𝖮i, where ⋯ indicates a tower of i exponentiations and ∃𝖧𝖮i is the class of queries that begin with existential quantifiers of ith order and then a formula of (i − 1)th order.[4]

Notes

edit edit source
  1. ^ "ELEMENTARY", Complexity Zoo, retrieved 2025-07-31
  2. ^ Friedman 1999.
  3. ^ Engelfriet 1991.
  4. ^ Hella & Turull-Torres 2006.

References

edit edit source Complexity classesConsidered feasible Suspected infeasible Considered infeasible Other complexity classes Class hierarchies Families of classes List of complexity classes

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371839387 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001371839387 · captured 1787940379.0 · version history

Cite this page as: encyclopegia.org, “ELEMENTARY”, snapshot enwiki-001371839387. https://encyclopegia.org/a/elementary