Defined in [Sch16]. Let and where is applied to itself times. For example , , etc. Then define, , note that this has the same growth rate as 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].
No class.