Nonelementary problem

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