Nonelementary problem

Template:Short description Template:CS1 config 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, $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 $F_0,F_1,\dots ,F_{\omega },F_{\omega +1},\dots$. For each ordinal $\alpha$, we define the class ${ℱ}_{\alpha }$ to be the class of functions computable in time $F_{\alpha }^{(k)}(n)$, for some positive constant $k$. Here, the notation $F^{(k)}$ indicates function iteration: it is the function obtained by applying $F$ repeatedly, $k$ times. That is, $${ℱ}_{\alpha }:=\bigcup _{k=1}^{\mathrm{\infty }}𝖥𝖣𝖳𝖨𝖬𝖤(F_{\alpha }^{(k)}(n))$$Now, define ${𝖥}_{\alpha }$ to be the complexity class $\bigcup _{\beta <\alpha ,p\in {ℱ}_{\beta }}𝖣𝖳𝖨𝖬𝖤(F_{\alpha }(p(n)))$.

With the definition, we have

• ELEMENTARY: the class of problems decidable in time $f(n)$, where $f(n)$ is a fixed-height exponential tower function. In other words, $𝖤𝖫𝖤𝖬𝖤𝖭𝖳𝖠𝖱𝖸=𝖣𝖳𝖨𝖬𝖤(n)\cup 𝖣𝖳𝖨𝖬𝖤(2^n)\cup 𝖣𝖳𝖨𝖬𝖤(2^{2^n})\cup \cdots$.
• TOWER: $f(n)={}^{p(n)}2$, where $p(n)$ is a fixed-height exponential tower function, and the superscript denotes tetration. In other words, $f(n)=F_3(p(n))$. In other words, $𝖳𝖮𝖶𝖤𝖱=𝖣𝖳𝖨𝖬𝖤({}^{n}2)\cup 𝖣𝖳𝖨𝖬𝖤({}^{2^n}2)\cup 𝖣𝖳𝖨𝖬𝖤({}^{2^{2^n}}2)\cup \cdots$. In other words, $𝖳𝖮𝖶𝖤𝖱:={𝖥}_3$.
• PR: $f(n)$ is a primitive recursive function. In other words, $𝖯𝖱=𝖣𝖳𝖨𝖬𝖤(F_1)\cup 𝖣𝖳𝖨𝖬𝖤(F_2)\cup 𝖣𝖳𝖨𝖬𝖤(F_3)\cup \cdots$.
• ACK: $f(n)=A(n,n)=F_{\omega }(n)$, where $A$ is the Ackermann function. In other words, $𝖠𝖢𝖪:={𝖥}_{\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 $\mathrm{Reach}(V_1),\mathrm{Reach}(V_2)$, decide whether $\mathrm{Reach}(V_1)\subset \mathrm{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 ${𝖥}_{\omega },{𝖥}_{{\omega }^{\omega }},{𝖥}_{{\omega }^{{\omega }^{\omega }}},$ or ${𝖥}_{{ϵ}_0}$-complete.

A large list is collected in.

References

Template:Asbox