# Ackermann Function Time Complexity

Are there any known problems that have an Ackermann function time complexity lower bound?

• I think we find it very hard to give time complexity lower bounds even for prosaic functions like $n^2$. You may not find anything beyond silly answers like "output the Ackermann function in unary". Also, the Ackermann function seems somewhat contrived, so it seems a bit strange if it is naturally the number of steps needed to solve some other problem. – usul Oct 19 '14 at 19:10
• I do know that the fastest non-randomized comparison-based algorithm with known complexity for creating a minimum spanning tree has a running time of O(m α(m,n)), where α is the classical functional inverse of the Ackermann function. This being the case one would think there might be a problem that requires running time based off the non inverted Ackermann function. – Tony Johnson Oct 19 '14 at 22:16
• Doesn't the time-hierarchy theorem answer this question? – Sasho Nikolov Oct 19 '14 at 22:44

What is even more interesting is that there are complete problems for Ackermannian time, under say primitive-recursive many-one reductions: define for this $$\mathsf{Ack}=\bigcup_{f\text{ Primitive-Recursive}}\mathsf{DTime}\big(ack(f(n))\big)\;.$$
• input: Two VAS $V_1$, $V_2$ with $\text{Reach}(V_1)$ and $\text{Reach}(V_2)$ finite.
• question: $\text{Reach}(V_1)\subseteq\text{Reach}(V_2)$?
This was shown non primitive-recursive (in a uniform way, thus $\mathsf{Ack}$-hard according to the above definition) by Mayr and Meyer in 1981 (there is a simpler proof published by Jančar in 2001). An $\mathsf{Ack}$ upper bound was first proved by McAloon (1984), with a simpler proof (but slightly worse bound) by Clote (1986), and improved and simplified arguments by Figueira et al. (2011).
Many problems are shown $\mathsf{Ack}$-hard through reductions from the reachability problem in lossy counter machines (or slight variants). Those can be defined as Minsky machines where counter values may decrease in an uncontrolled way; see Schnoebelen 2002 & 2010 and Urquhart (1999) for a similar construction.