NONELEMENTARY

In computational complexity theory, the complexity class NONELEMENTARY is the complement of the class ELEMENTARY.

Example decidable problems in NONELEMENTARY this class are:

• the problem of regular expression equivalence with not
• decision problem for monadic second-order logic over trees
• decision problem for term algebras