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. That is, it includes all decision problems that has no algorithmic solution with time bounded by an elementary recursive function. These functions grow no faster than a fixed-height tower of exponentiation). Not all primitive recursive functions are elementary; for example, tetration grows too rapidly to be included in the elementary class.

The hierarchy of decidable problems beyond the elementary is usually presented along the fast-growing hierarchy.

. For each ordinal indicates function iteration.

With the definition, we have

• .

• is a fixed-height exponential tower function, and the superscript denotes tetration.

• is a primitive recursive function.

• is the Ackermann function

By the time-hierarchy theorem, ELEMENTARY and PR have no complete problems. However, TOWER and ACK do have complete problems.

TOWER-complete problems:

• Star-Free Expression Equivalence (SFEq)

• Satisfiability of the Weak Monadic Second-Order Logic of One Successor (WS1S)

• Satisfiability of W. V. O. Quine's fluted fragment of first-order logic

• β-convertibility of two closed terms in simply typed lambda calculus

ACK-complete problems:

• reachability in vector addition systems (VAS).

• reachability in labeled vector addition system with states (VASS)

• reachability in Petri nets.

Other nonelementary but decidable problems:

• 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

• . Its precise level of complexity is unknown. Note that deciding whether the reachable set is finite is EXPSPACE-complete.

• The Coverability and Termination problems of certain classes of well-structured transition systems-complete.

A large list is collected in.

References