- Source: Nonelementary problem
In computational complexity theory, a nonelementary problem 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)
the decision problem for term algebras
satisfiability of W. V. O. Quine's fluted fragment of first-order logic
deciding β-convertibility of two closed terms in typed lambda calculus
reachability in vector addition systems; it is Ackermann-complete.
reachability in Petri nets; it is Ackermann-complete.