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 monadic second-order theory with two successors (see S2S)
- the first-order theory of any term algebra in a signature containing at least one binary function symbol
- 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.
wikipedia, wiki, encyclopedia, book, library, article, read, free download, Information about Nonelementary problem, What is Nonelementary problem? What does Nonelementary problem mean?