<p>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 <a href="http://arxiv.org/abs/1312.5686">Complexity Hierarchies Beyond Elementary</a>.</p>

<p>What is even more interesting is that there are <em>complete</em> 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)\;.$$</p>

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

<ul><li>input: Two VAS $V_1$, $V_2$ with $\text{Reach}(V_1)$ and $\text{Reach}(V_2)$ finite.</li><li>question: $\text{Reach}(V_1)\subseteq\text{Reach}(V_2)$?</li></ul>

<p>This was shown non primitive-recursive (in a uniform way, thus $\mathsf{Ack}$-hard according to the above definition) by <a href="http://dx.doi.org/10.1145/322261.322271">Mayr and Meyer in 1981</a> (there is a simpler proof published by <a href="http://dx.doi.org/10.1016/S0304-3975(00)00100-6">Jančar in 2001</a>).  An $\mathsf{Ack}$ upper bound was first proved by <a href="http://dx.doi.org/10.1016/0304-3975(84)90029-X">McAloon (1984)</a>, with a simpler proof (but slightly worse bound) by <a href="http://dx.doi.org/10.1016/0304-3975(86)90169-6">Clote (1986)</a>, and improved and simplified arguments by <a href="http://dx.doi.org/10.1109/LICS.2011.39">Figueira et al. (2011)</a>.</p>

<p>Many problems are shown $\mathsf{Ack}$-hard through reductions from the <b>reachability</b> problem in <em>lossy counter machines</em> (or slight variants).  Those can be defined as Minsky machines where counter values may decrease in an uncontrolled way; see <a href="http://dx.doi.org/10.1016/S0020-0190(01)00337-4">Schnoebelen 2002</a><a href="http://dx.doi.org/10.1007/978-3-642-15155-2_54"> &amp; 2010</a> and <a href="http://dx.doi.org/10.2307/2586811">Urquhart (1999)</a> for a similar construction.</p>

CC BY-SA 3.0
2014-10-20T10:40:22.730Z
2014-10-20T10:40:22.730Z
Sylvain
<p>Are there any known problems that have an Ackermann function time complexity lower bound?</p>

CC BY-SA 3.0
2014-10-19T19:10:54.597Z
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
CC BY-SA 3.0
2014-10-19T22:16:37.500Z
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
CC BY-SA 3.0
2014-10-19T22:44:54.523Z
Doesn't the time-hierarchy theorem answer this question?
Sasho Nikolov
<cc.complexity-theory><lower-bounds>
Ackermann Function Time Complexity
Tony Johnson
# Ackermann Function Time Complexity

(Asked by: username_0 on 2014-10-19)

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

**Tags:** cc.complexity-theory, lower-bounds
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: Doesn't the time-hierarchy theorem answer this question?  

---

## 1 answers

### Answer by username_3 on 2014-10-20. Score: 15 | Accepted answer

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](http://arxiv.org/abs/1312.5686).

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](http://dx.doi.org/10.1145/322261.322271) (there is a simpler proof published by [Jančar in 2001](http://dx.doi.org/10.1016/S0304-3975(00)00100-6)). An $\mathsf{Ack}$ upper bound was first proved by [McAloon (1984)](http://dx.doi.org/10.1016/0304-3975(84)90029-X), with a simpler proof (but slightly worse bound) by [Clote (1986)](http://dx.doi.org/10.1016/0304-3975(86)90169-6), and improved and simplified arguments by [Figueira et al. (2011)](http://dx.doi.org/10.1109/LICS.2011.39).

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](http://dx.doi.org/10.1016/S0020-0190(01)00337-4) [& 2010](http://dx.doi.org/10.1007/978-3-642-15155-2_54) and [Urquhart (1999)](http://dx.doi.org/10.2307/2586811) for a similar construction.


---

