Sample Page

In computational complexity theory, a nonelementary problem^[1] is a problem that is not a member of the class 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. These functions grow no faster than a fixed-height tower of exponentiation (for example, $O(2^{2^{n}})$ ). Not all primitive recursive functions are elementary; for example, 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.^[2]

Let the functions of the hierarchy be $F_{0},F_{1},\dots ,F_{\omega },F_{\omega +1},\dots$ . For each ordinal $\alpha$ , we define the class ${\mathcal {F}}_{\alpha }$ to be the class of functions computable in time $F_{\alpha }(n)^{k}$ , for some positive constant $k$ . That is, ${\mathcal {F}}_{\alpha }:=\bigcup _{k=1}^{\infty }{\mathsf {FDTIME}}(F_{\alpha }^{k}(n))$ Now, define ${\mathsf {F}}_{\alpha }$ to be the complexity class $\bigcup _{\beta <\alpha ,p\in {\mathcal {F}}_{\beta }}{\mathsf {DTIME}}(F_{\alpha }(p(n)))$ .

With the definition, we have

ELEMENTARY: the class of problems decidable in time $f(n)$ , where $f(n)$ is a fixed-height exponential tower function. In other words, ${\mathsf {ELEMENTARY}}={\mathsf {DTIME}}(n)\cup {\mathsf {DTIME}}(2^{n})\cup {\mathsf {DTIME}}(2^{2^{n}})\cup \cdots$ .
TOWER: $f(n)={\;}^{p(n)}2$ , where $p(n)$ is a fixed-height exponential tower function, and the superscript denotes tetration. In other words, $f(n)=F_{3}(p(n))$ . In other words, ${\mathsf {TOWER}}={\mathsf {DTIME}}({}^{n}2)\cup {\mathsf {DTIME}}({}^{2^{n}}2)\cup {\mathsf {DTIME}}({}^{2^{2^{n}}}2)\cup \cdots$ . In other words, ${\mathsf {TOWER}}:={\mathsf {F}}_{3}$ .
PR: $f(n)$ is a primitive recursive function. In other words, ${\mathsf {PR}}={\mathsf {DTIME}}(F_{1})\cup {\mathsf {DTIME}}(F_{2})\cup {\mathsf {DTIME}}(F_{3})\cup \cdots$ .
ACK: $f(n)=A(n,n)=F_{\omega }(n)$ , where $A$ is the Ackermann function. In other words, ${\mathsf {ACK}}:={\mathsf {F}}_{\omega }$

By the 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)^[2]
Satisfiability of the Weak Monadic Second-Order Logic of One Successor (WS1S)^[2]
Satisfiability of W. V. O. Quine‘s fluted fragment of first-order logic^[3]
β-convertibility of two closed terms in simply typed lambda calculus^[4]^[5]

ACK-complete problems:

reachability in vector addition systems (VAS).^[6]^[7]
reachability in labeled vector addition system with states (VASS)^[8]
reachability in Petri nets.^[9]^[7]

Other nonelementary but decidable problems:

the problem of regular expression equivalence with complementation^[10]
the monadic second-order theory with two successors (see S2S)^[11]
the first-order theory of any term algebra in a signature containing at least one binary function symbol^[12]
finite containment problem (FCP): Given two VAS with finite reachable sets $\operatorname {Reach} (V_{1}),\operatorname {Reach} (V_{2})$ , decide whether $\operatorname {Reach} (V_{1})\subset \operatorname {Reach} (V_{2})$ . Its precise level of complexity is unknown. Note that deciding whether the reachable set is finite is EXPSPACE-complete.^[2]
The Coverability and Termination problems of certain classes of well-structured transition systems are known to be ${\mathsf {F}}_{\omega },{\mathsf {F}}_{\omega ^{\omega }},{\mathsf {F}}_{\omega ^{\omega ^{\omega }}},$ or ${\mathsf {F}}_{\epsilon _{0}}$ -complete.^[13]

A large list is collected in ^[2].

References

^ Vorobyov, Sergei; Voronkov, Andrei (1998), “Complexity of Nonrecursive Logic Programs with Complex Values”, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS ’98), New York, NY, USA: ACM, pp. 244–253, CiteSeerX 10.1.1.39.8822, doi:10.1145/275487.275515, ISBN 978-0-89791-996-8, S2CID 15631793.
^ ^a ^b ^c ^d ^e Schmitz, Sylvain (2016-02-03). “Complexity Hierarchies beyond Elementary”. ACM Transactions on Computation Theory. 8 (1): 1–36. arXiv:1312.5686. doi:10.1145/2858784. ISSN 1942-3454.
^ Pratt-Hartmann, Ian; Szwast, Wiesław; Tendera, Lidia (2019). “The Fluted Fragment Revisited”. The Journal of Symbolic Logic. 84 (3): 1020–1048. doi:10.1017/jsl.2019.33. ISSN 0022-4812. JSTOR 26788488.
^ Statman, Richard (1979), “The typed λ-calculus is not elementary recursive”, Theoretical Computer Science, 9: 73–81, doi:10.1016/0304-3975(79)90007-0, hdl:2027.42/23535.
^ Nguyên, Lê Thành Dũng (2024-09-05). “Simply typed convertibility is TOWER-complete even for safe lambda-terms”. Logical Methods in Computer Science. 20 (3) 11344. doi:10.46298/lmcs-20(3:21)2024. ISSN 1860-5974.
^ Czerwiński, Wojciech; Orlikowski, Łukasz (2021). Reachability in Vector Addition Systems is Ackermann-complete. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). arXiv:2104.13866.
^ ^a ^b Brubaker, Ben (4 December 2023). “An Easy-Sounding Problem Yields Numbers Too Big for Our Universe”. Quanta Magazine.
^ Hofman, Piotr; Totzke, Patrick (2014). Ouaknine, Joël; Potapov, Igor; Worrell, James (eds.). “Trace Inclusion for One-Counter Nets Revisited”. Reachability Problems. Cham: Springer International Publishing: 151–162. doi:10.1007/978-3-319-11439-2_12. ISBN 978-3-319-11439-2.
^ Leroux, Jerome (February 2022). “The Reachability Problem for Petri Nets is Not Primitive Recursive”. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 1241–1252. arXiv:2104.12695. doi:10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6.
^ Stockmeyer, Larry J. (1974), The Complexity of Decision Problems in Automata Theory and Logic (PDF), Ph.D. dissertation, Massachusetts Institute of Technology
^ Libkin, Leonid (2006), “Logics for unranked trees: an overview”, Logical Methods in Computer Science, 2 (3) 2244: 3:2, 31, arXiv:cs.LO/0606062, doi:10.2168/LMCS-2(3:2)2006, MR 2295773.
^ Vorobyov, Sergei (1996), “An improved lower bound for the elementary theories of trees”, Automated Deduction — CADE-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1104, Springer, pp. 275–287, CiteSeerX 10.1.1.39.1499, doi:10.1007/3-540-61511-3_91, ISBN 978-3-540-61511-8.
^ Schmitz, Sylvain; Schnoebelen, Philippe (2013). “The Power of Well-Structured Systems”. In D’Argenio, Pedro R.; Melgratti, Hernán (eds.). CONCUR 2013 – Concurrency Theory. Lecture Notes in Computer Science. Vol. 8052. Berlin, Heidelberg: Springer. pp. 5–24. arXiv:1402.2908. doi:10.1007/978-3-642-40184-8_2. ISBN 978-3-642-40184-8.

[rdp-we-cite_note-1] Vorobyov, Sergei; Voronkov, Andrei (1998), “Complexity of Nonrecursive Logic Programs with Complex Values”, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS ’98), New York, NY, USA: ACM, pp. 244–253, CiteSeerX 10.1.1.39.8822, doi:10.1145/275487.275515, ISBN 978-0-89791-996-8, S2CID 15631793.

[rdp-we-cite_note-:1-2] Schmitz, Sylvain (2016-02-03). “Complexity Hierarchies beyond Elementary”. ACM Transactions on Computation Theory. 8 (1): 1–36. arXiv:1312.5686. doi:10.1145/2858784. ISSN 1942-3454.

[rdp-we-cite_note-3] Pratt-Hartmann, Ian; Szwast, Wiesław; Tendera, Lidia (2019). “The Fluted Fragment Revisited”. The Journal of Symbolic Logic. 84 (3): 1020–1048. doi:10.1017/jsl.2019.33. ISSN 0022-4812. JSTOR 26788488.

[rdp-we-cite_note-4] Statman, Richard (1979), “The typed λ-calculus is not elementary recursive”, Theoretical Computer Science, 9: 73–81, doi:10.1016/0304-3975(79)90007-0, hdl:2027.42/23535.

[rdp-we-cite_note-5] Nguyên, Lê Thành Dũng (2024-09-05). “Simply typed convertibility is TOWER-complete even for safe lambda-terms”. Logical Methods in Computer Science. 20 (3) 11344. doi:10.46298/lmcs-20(3:21)2024. ISSN 1860-5974.

[rdp-we-cite_note-6] Czerwiński, Wojciech; Orlikowski, Łukasz (2021). Reachability in Vector Addition Systems is Ackermann-complete. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). arXiv:2104.13866.

[rdp-we-cite_note-:0-7] Brubaker, Ben (4 December 2023). “An Easy-Sounding Problem Yields Numbers Too Big for Our Universe”. Quanta Magazine.

[rdp-we-cite_note-8] Hofman, Piotr; Totzke, Patrick (2014). Ouaknine, Joël; Potapov, Igor; Worrell, James (eds.). “Trace Inclusion for One-Counter Nets Revisited”. Reachability Problems. Cham: Springer International Publishing: 151–162. doi:10.1007/978-3-319-11439-2_12. ISBN 978-3-319-11439-2.

[rdp-we-cite_note-9] Leroux, Jerome (February 2022). “The Reachability Problem for Petri Nets is Not Primitive Recursive”. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 1241–1252. arXiv:2104.12695. doi:10.1109/FOCS52979.2021.00121. ISBN 978-1-6654-2055-6.

[rdp-we-cite_note-10] Stockmeyer, Larry J. (1974), The Complexity of Decision Problems in Automata Theory and Logic (PDF), Ph.D. dissertation, Massachusetts Institute of Technology

[rdp-we-cite_note-11] Libkin, Leonid (2006), “Logics for unranked trees: an overview”, Logical Methods in Computer Science, 2 (3) 2244: 3:2, 31, arXiv:cs.LO/0606062, doi:10.2168/LMCS-2(3:2)2006, MR 2295773.

[rdp-we-cite_note-12] Vorobyov, Sergei (1996), “An improved lower bound for the elementary theories of trees”, Automated Deduction — CADE-13: 13th International Conference on Automated Deduction New Brunswick, NJ, USA, July 30 – August 3, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1104, Springer, pp. 275–287, CiteSeerX 10.1.1.39.1499, doi:10.1007/3-540-61511-3_91, ISBN 978-3-540-61511-8.

[rdp-we-cite_note-13] Schmitz, Sylvain; Schnoebelen, Philippe (2013). “The Power of Well-Structured Systems”. In D’Argenio, Pedro R.; Melgratti, Hernán (eds.). CONCUR 2013 – Concurrency Theory. Lecture Notes in Computer Science. Vol. 8052. Berlin, Heidelberg: Springer. pp. 5–24. arXiv:1402.2908. doi:10.1007/978-3-642-40184-8_2. ISBN 978-3-642-40184-8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Complexity classes
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC 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 NONELEMENTARY PR R RE ALL
Other complexity classes	polyL QP
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