Defined in [Sch16] as the union of DTIME(F3(p(n))) over all elementary functions p(n), where F3 is the third level of the fast growing hierarchy, i.e., the iterated exponential function. The author describes this as the class of problems that are not in ELEMENTARY but only barely so. Unlike ELEMENTARY and PR, which have no complete problems, Tower has several natural examples of complete problems (under elementary reductions). Specifically, the Star-Free Expression Equivalence (SFEq) problem is complete for this class, as is the satisfiability of the Weak Monadic Theory of One Successor (WS1S).
Strictly contains ELEMENTARY and is strictly contained in PR.
Note that the same class is obtained if DTIME is replaced by NTIME or DSPACE in the definition.
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].
Equals the union of DTIME(2n), DTIME(22n), DTIME(222n), and so on.
