# Nonelementary problem

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Nonelementary_problem
> Markdown URL: https://mediated.wiki/source/Nonelementary_problem.md
> Source: https://en.wikipedia.org/wiki/Nonelementary_problem
> Source revision: 1353767963
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Computational problem with high complexity}}
{{CS1 config|mode=cs2}}
In [computational complexity theory](/source/computational_complexity_theory), a  '''nonelementary problem'''<ref>{{citation
 | last1 = Vorobyov | first1 = Sergei
 | last2 = Voronkov | first2 = Andrei|author2link = Andrei Voronkov (computer scientist)
 | contribution = Complexity of Nonrecursive Logic Programs with Complex Values
 | doi = 10.1145/275487.275515
 | isbn = 978-0-89791-996-8
 | location = New York, NY, USA
 | pages = 244–253
 | publisher = ACM
 | title = Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART [Symposium on Principles of Database Systems](/source/Symposium_on_Principles_of_Database_Systems) (PODS '98)
 | year = 1998| citeseerx = 10.1.1.39.8822
 | s2cid = 15631793
 }}.</ref> is a problem that is not a member of the class [ELEMENTARY](/source/ELEMENTARY). As a class it is sometimes denoted as NONELEMENTARY. That is, it includes all decision problems that has no algorithmic solution with time bounded by an [elementary recursive function](/source/elementary_recursive_function). These functions grow no faster than a fixed-height tower of [exponentiation](/source/exponentiation) (for example, <math>O(2^{2^n})</math>). Not all primitive recursive functions are elementary; for example, [tetration](/source/tetration) grows too rapidly to be included in the elementary class.

The hierarchy of decidable problems beyond the elementary is usually presented along the [fast-growing hierarchy](/source/fast-growing_hierarchy).<ref name=":1">{{citation |last=Schmitz |first=Sylvain |date=2016-02-03 |title=Complexity Hierarchies beyond Elementary |url=https://dl.acm.org/doi/10.1145/2858784 |journal=ACM Transactions on Computation Theory |language=en |volume=8 |issue=1 |pages=1–36 |doi=10.1145/2858784 |arxiv=1312.5686 |issn=1942-3454}}</ref>

Let the functions of the hierarchy be <math>F_0, F_1, \dots, F_\omega, F_{\omega+1}, \dots</math>. For each [ordinal](/source/Ordinal_number) <math>\alpha</math>, we define the class <math>\mathcal F_\alpha</math> to be the class of functions computable in time <math>F_\alpha^{(k)}(n)</math>, for some positive constant <math>k</math>. Here, the notation <math>F^{(k)}</math> indicates [function iteration](/source/function_iteration): it is the function obtained by applying <math>F</math> repeatedly, <math>k</math> times. That is, <math display="block">\mathcal F_\alpha := \bigcup_{k = 1}^\infty \mathsf{FDTIME}(F_\alpha^{(k)}(n))</math>Now, define <math>\mathsf{F}_\alpha</math> to be the complexity class <math>\bigcup_{\beta < \alpha, p \in \mathcal F_\beta} \mathsf{DTIME}(F_\alpha(p(n)))</math>.

With the definition, we have

* ELEMENTARY: the class of problems decidable in time <math>f(n)</math>, where <math>f(n)</math> is a fixed-height exponential tower function. In other words, <math>\mathsf{ELEMENTARY} = \mathsf{DTIME}(n) \cup \mathsf{DTIME}(2^n) \cup \mathsf{DTIME}(2^{2^n}) \cup \cdots</math>.
* TOWER: <math>f(n) = {\;}^{p(n)}2</math>, where <math>p(n)</math> is a fixed-height exponential tower function, and the superscript denotes [tetration](/source/tetration). In other words, <math>f(n) = F_3(p(n))</math>. In other words, <math>\mathsf{TOWER} = \mathsf{DTIME}({}^n2) \cup \mathsf{DTIME}({}^{2^n}2) \cup \mathsf{DTIME}({}^{2^{2^n}}2) \cup \cdots</math>. In other words, <math>\mathsf{TOWER} := \mathsf{F}_3</math>.
* PR: <math>f(n)</math> is a [primitive recursive function](/source/primitive_recursive_function). In other words, <math>\mathsf{PR} = \mathsf{DTIME}(F_1) \cup \mathsf{DTIME}(F_2) \cup \mathsf{DTIME}(F_3) \cup \cdots</math>.
* ACK: <math>f(n) = A(n, n) = F_\omega(n)</math>, where <math>A</math> is the [Ackermann function](/source/Ackermann_function). In other words, <math>\mathsf{ACK} := \mathsf{F}_\omega</math>

By the [time-hierarchy theorem](/source/Time_hierarchy_theorem), ELEMENTARY and PR have no complete problems. However, TOWER and ACK do have complete problems.

'''TOWER'''-complete problems:

* Star-Free Expression Equivalence (SFEq)<ref name=":1" />
* Satisfiability of the [Weak Monadic Second-Order Logic of One Successor](/source/Monadic_second-order_logic) (WS1S)<ref name=":1" />
* Satisfiability of [W. V. O. Quine](/source/W._V._O._Quine)'s fluted fragment of [first-order logic](/source/first-order_logic)<ref>{{citation |last1=Pratt-Hartmann |first1=Ian |last2=Szwast |first2=Wiesław |last3=Tendera |first3=Lidia |date=2019 |title=The Fluted Fragment Revisited |url=https://www.jstor.org/stable/26788488 |journal=The Journal of Symbolic Logic |volume=84 |issue=3 |pages=1020–1048 |doi=10.1017/jsl.2019.33 |jstor=26788488 |issn=0022-4812}}</ref>
* β-convertibility of two closed terms in [simply typed lambda calculus](/source/simply_typed_lambda_calculus)<ref>{{citation
 | last = Statman | first = Richard|authorlink = Richard Statman
 | title = The typed λ-calculus is not elementary recursive
 | doi = 10.1016/0304-3975(79)90007-0
 | journal = [Theoretical Computer Science](/source/Theoretical_Computer_Science_(journal))
 | volume = 9
 | pages = 73–81
 | year = 1979
 | hdl = 2027.42/23535
 | hdl-access = free
 }}.</ref><ref>{{citation |last=Nguyên |first=Lê Thành Dũng |date=2024-09-05 |title=Simply typed convertibility is TOWER-complete even for safe lambda-terms |url=https://lmcs.episciences.org/11344 |journal=Logical Methods in Computer Science |language=en |volume=20 |issue=3 |article-number=11344 |doi=10.46298/lmcs-20(3:21)2024 |issn=1860-5974}}</ref>

'''ACK'''-complete problems:
* [reachability](/source/Reachability_problem) in [vector addition system](/source/vector_addition_system)s (VAS).<ref>{{citation |last1=Czerwiński |first1=Wojciech |last2=Orlikowski |first2=Łukasz |contribution=Reachability in Vector Addition Systems is Ackermann-complete | date=2021 | title=2021 IEEE 62nd Annual [Symposium on Foundations of Computer Science](/source/Symposium_on_Foundations_of_Computer_Science) (FOCS) | arxiv=2104.13866}}</ref><ref name=":0">{{citation |last=Brubaker |first=Ben |date=4 December 2023 |title=An Easy-Sounding Problem Yields Numbers Too Big for Our Universe |url=https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ |website=[Quanta Magazine](/source/Quanta_Magazine)}}</ref>
* reachability in labeled vector addition system with states (VASS)<ref>{{citation |last=Hofman |first=Piotr |last2=Totzke |first2=Patrick |date=2014 |editor-last=Ouaknine |editor-first=Joël |editor2-last=Potapov |editor2-first=Igor |editor3-last=Worrell |editor3-first=James |title=Trace Inclusion for One-Counter Nets Revisited |url=https://link.springer.com/chapter/10.1007/978-3-319-11439-2_12?error=cookies_not_supported&code=28834659-0011-4257-ae10-52282a24131b |journal=Reachability Problems |language=en |location=Cham |publisher=Springer International Publishing |pages=151–162 |doi=10.1007/978-3-319-11439-2_12 |isbn=978-3-319-11439-2}}</ref>
* [reachability](/source/Reachability_problem) in [Petri nets](/source/Petri_net).<ref>{{citation |last=Leroux |first=Jerome |chapter=The Reachability Problem for Petri Nets is Not Primitive Recursive |date=February 2022 |title=2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |publisher=IEEE |pages=1241–1252 |doi=10.1109/FOCS52979.2021.00121 |isbn=978-1-6654-2055-6|arxiv=2104.12695 }}</ref><ref name=":0" />
Other nonelementary but decidable problems:
* the problem of [regular expression equivalence with complementation](/source/Regular_expression)<ref>{{citation|first=Larry J.|last=Stockmeyer|authorlink=Larry Stockmeyer|title=The Complexity of Decision Problems in Automata Theory and Logic|series=Ph.D. dissertation|year=1974|url=http://people.csail.mit.edu/meyer/Stockmeyer-thesis.pdf|publisher=Massachusetts Institute of Technology}}</ref>
* the [monadic second-order](/source/monadic_second-order) [theory](/source/theory_(logic)) with two successors (see [S2S](/source/S2S_(mathematics)))<ref>{{citation
 | last = Libkin | first = Leonid|authorlink = Leonid Libkin
 | arxiv = cs.LO/0606062
 | doi = 10.2168/LMCS-2(3:2)2006
 | issue = 3
 | journal = [Logical Methods in Computer Science](/source/Logical_Methods_in_Computer_Science)
 | mr = 2295773
 | page = 3:2, 31
 | title = Logics for unranked trees: an overview
 | volume = 2
 | year = 2006| article-number = 2244}}.</ref>
* the [first-order](/source/first-order_logic) theory of any [term algebra](/source/term_algebra) in a signature containing at least one binary function symbol<ref>{{citation
 | last = Vorobyov | first = Sergei
 | contribution = An improved lower bound for the elementary theories of trees
 | doi = 10.1007/3-540-61511-3_91
 | pages = 275–287
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Automated Deduction — CADE-13: 13th International [Conference on Automated Deduction](/source/Conference_on_Automated_Deduction) New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings
 | volume = 1104
 | year = 1996| isbn = 978-3-540-61511-8
 | citeseerx = 10.1.1.39.1499
 }}.</ref>
* finite containment problem (FCP): Given two VAS with finite reachable sets <math>\operatorname{Reach}(V_1), \operatorname{Reach}(V_2)</math>, decide whether <math>\operatorname{Reach}(V_1) \subset \operatorname{Reach}(V_2)</math>. Its precise level of complexity is unknown. Note that deciding whether the reachable set is finite is EXPSPACE-complete.<ref name=":1" />
* The Coverability and Termination problems of certain classes of [well-structured transition systems](/source/Well-structured_transition_system) are known to be <math>\mathsf{F}_\omega, \mathsf{F}_{\omega^\omega}, \mathsf{F}_{\omega^{\omega^\omega}},</math> or <math>\mathsf{F}_{\epsilon_0}</math>-complete.<ref>{{citation |last1=Schmitz |first1=Sylvain |last2=Schnoebelen |first2=Philippe |date=2013 |editor-last=D’Argenio |editor-first=Pedro R. |chapter=The Power of Well-Structured Systems |series=Lecture Notes in Computer Science |volume=8052 |editor2-last=Melgratti |editor2-first=Hernán |title=CONCUR 2013 – Concurrency Theory |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=5–24 |doi=10.1007/978-3-642-40184-8_2 |arxiv=1402.2908 |isbn=978-3-642-40184-8}}</ref>
A large list is collected in.<ref name=":1" />

==References==
{{reflist}}

{{Complexity classes}}

{{DEFAULTSORT:Nonelementary}}
Category:Complexity classes

{{Comp-sci-theory-stub}}

---
Adapted from the Wikipedia article [Nonelementary problem](https://en.wikipedia.org/wiki/Nonelementary_problem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Nonelementary_problem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.