Class Description

Ack: Ackermann Time

Defined in [Sch16]. Let ${\displaystyle F_{0}(x)=x+1}$ and ${\displaystyle F_{k}(x)=F_{k-1}^{x}(x)}$ where ${\displaystyle F_{k-1}^{x}(x)}$ is ${\displaystyle F_{k-1}(x)}$ applied to itself ${\displaystyle x}$ times. For example ${\displaystyle F_{1}(x)=2x+1}$, ${\displaystyle F_{2}(x)=2^{x+1}(x+1)-1}$, etc. Then define, ${\displaystyle F_{\omega }(x)=F_{x}(x)}$, note that this has the same growth rate as ${\displaystyle A(x,x)}$ where A is the Ackermann function. This class is equal to DTIME(F_ω(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace DTIME with NTIME or DSPACE.

Strictly contains ELEMENTARY, Tower, and PR. Is strictly contained in R.

The relationship between this class and PR is analogous to the relationship between Tower and ELEMENTARY. That is, Ack contains problems "barely" outside of PR and, unlike PR, has complete problems.

The reachability problems for Petri nets [Ler22] and vector addition systems [CO22] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [Ani+23].

Linked From

No class.