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. 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, ${\displaystyle O(2^{2^{n}})}$). 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 ${\displaystyle F_{0},F_{1},\dots ,F_{\omega },F_{\omega +1},\dots }$. For each ordinal ${\displaystyle \alpha }$, we define the class ${\displaystyle {\mathcal {F}}_{\alpha }}$ to be the class of functions computable in time ${\displaystyle F_{\alpha }^{(k)}(n)}$, for some positive constant ${\displaystyle k}$. Here, the notation ${\displaystyle F^{(k)}}$ indicates function iteration: it is the function obtained by applying ${\displaystyle F}$ repeatedly, ${\displaystyle k}$ times. That is, $${\displaystyle {\mathcal {F}}_{\alpha }:=\bigcup _{k=1}^{\infty }{\mathsf {FDTIME}}(F_{\alpha }^{(k)}(n))}$$Now, define ${\displaystyle {\mathsf {F}}_{\alpha }}$ to be the complexity class ${\displaystyle \bigcup _{\beta <\alpha ,p\in {\mathcal {F}}_{\beta }}{\mathsf {DTIME}}(F_{\alpha }(p(n)))}$.

With the definition, we have

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

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
• finite containment problem (FCP): Given two VAS with finite reachable sets ${\displaystyle \operatorname {Reach} (V_{1}),\operatorname {Reach} (V_{2})}$, decide whether ${\displaystyle \operatorname {Reach} (V_{1})\subset \operatorname {Reach} (V_{2})}$. 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 are known to be ${\displaystyle {\mathsf {F}}_{\omega },{\mathsf {F}}_{\omega ^{\omega }},{\mathsf {F}}_{\omega ^{\omega ^{\omega }}},}$ or ${\displaystyle {\mathsf {F}}_{\epsilon _{0}}}$-complete.

A large list is collected in.

References