Nonelementary problem explained

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.

Examples of nonelementary problems that are nevertheless decidable include:

• the problem of regular expression equivalence with complementation
• the decision problem for monadic second-order logic over trees (see S2S)^[2]
• the decision problem for term algebras^[3]
• satisfiability of W. V. O. Quine's fluted fragment of first-order logic
• deciding β-convertibility of two closed terms in typed lambda calculus^[4]
• reachability in vector addition systems; it is Ackermann-complete.^{[5] [6]}
• reachability in Petri nets; it is Ackermann-complete.^[7]

Notes and References

1. .
2. .
3. .
4. .
5. Czerwiński . Wojciech . Orlikowski . Łukasz . Reachability in Vector Addition Systems is Ackermann-complete . 2021 . 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) . 2104.13866.
6. Web site: Brubaker . Ben . 4 December 2023 . An Easy-Sounding Problem Yields Numbers Too Big for Our Universe . Quanta Magazine.
7. Book: Leroux, Jerome . The Reachability Problem for Petri Nets is Not Primitive Recursive . February 2022 . 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) . https://ieeexplore.ieee.org/document/9719763 . IEEE . 1241–1252 . 10.1109/FOCS52979.2021.00121 . 978-1-6654-2055-6. 2104.12695 .