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

  • 2
    $\begingroup$ 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. $\endgroup$ – usul Oct 19 '14 at 19:10
  • 2
    $\begingroup$ 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. $\endgroup$ – Tony Johnson Oct 19 '14 at 22:16
  • 2
    $\begingroup$ Doesn't the time-hierarchy theorem answer this question? $\endgroup$ – Sasho Nikolov Oct 19 '14 at 22:44

There are "natural" problems hard for Ackermannian time; in fact there is a growing body of literature on the subject. A place to start is the survey in Section 6 of Complexity Hierarchies Beyond Elementary.

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)\;.$$

Many examples arise with counter systems and logics. For instance, the oldest known such problem is the inclusion problem between the sets of reachable configurations of two vector addition systems (VAS) assuming these sets to be finite:

  • 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.