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 (for example, <math>O(2^{2^n})</math>). 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.

Let the functions of the hierarchy be <math>F_0, F_1, \dots, F_\omega, F_{\omega+1}, \dots</math>. For each ordinal <math>\alpha</math>, we define the class <math>\mathcal F_\alpha</math> to be the class of functions computable in time <math>F_\alpha^{(k)}(n)</math>, for some positive constant <math>k</math>. Here, the notation <math>F^{(k)}</math> indicates function iteration: it is the function obtained by applying <math>F</math> repeatedly, <math>k</math> times. That is, <math display="block">\mathcal F_\alpha := \bigcup_{k = 1}^\infty \mathsf{FDTIME}(F_\alpha^{(k)}(n))</math>Now, define <math>\mathsf{F}_\alpha</math> to be the complexity class <math>\bigcup_{\beta < \alpha, p \in \mathcal F_\beta} \mathsf{DTIME}(F_\alpha(p(n)))</math>.

With the definition, we have

  • ELEMENTARY: the class of problems decidable in time <math>f(n)</math>, where <math>f(n)</math> is a fixed-height exponential tower function. In other words, <math>\mathsf{ELEMENTARY} = \mathsf{DTIME}(n) \cup \mathsf{DTIME}(2^n) \cup \mathsf{DTIME}(2^{2^n}) \cup \cdots</math>.
  • TOWER: <math>f(n) = {\;}^{p(n)}2</math>, where <math>p(n)</math> is a fixed-height exponential tower function, and the superscript denotes tetration. In other words, <math>f(n) = F_3(p(n))</math>. In other words, <math>\mathsf{TOWER} = \mathsf{DTIME}({}^n2) \cup \mathsf{DTIME}({}^{2^n}2) \cup \mathsf{DTIME}({}^{2^{2^n2) \cup \cdots</math>. In other words, <math>\mathsf{TOWER} := \mathsf{F}_3</math>.
  • PR: <math>f(n)</math> is a primitive recursive function. In other words, <math>\mathsf{PR} = \mathsf{DTIME}(F_1) \cup \mathsf{DTIME}(F_2) \cup \mathsf{DTIME}(F_3) \cup \cdots</math>.
  • ACK: <math>f(n) = A(n, n) = F_\omega(n)</math>, where <math>A</math> is the Ackermann function. In other words, <math>\mathsf{ACK} := \mathsf{F}_\omega</math>

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)
  • β-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.
  • 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
  • finite containment problem (FCP): Given two VAS with finite reachable sets <math>\operatorname{Reach}(V_1), \operatorname{Reach}(V_2)</math>, decide whether <math>\operatorname{Reach}(V_1) \subset \operatorname{Reach}(V_2)</math>. Its precise level of complexity is unknown. Note that deciding whether the reachable set is finite is EXPSPACE-complete.

A large list is collected in.