20
$\begingroup$

Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant inverse Ackermann term is ignored.

Are there any examples of known algorithms with running times that involve functions that grow fundamentally slower than inverse Ackermann (e.g. inverses of functions that are not equivalent to Ackermann under polynomial or exponential etc. transformations), that give the best-known worst-case time complexity for solving the underlying problem?

$\endgroup$
  • 2
    $\begingroup$ $O(1)$ time algorithms? You're asking about a known problem whose best known algorithm is $\omega(1)$ and $o(\alpha(n))$? First you need to find a function growing "fundamentally faster" than $A(n)$, like TREE$(n)$, and then take its inverse, and then find a problem that fits it! $\endgroup$ – Pål GD Sep 18 '13 at 22:48
  • 1
    $\begingroup$ there are arbitrary contrived algorithms built out of the time hierarchy thm $\endgroup$ – vzn Sep 19 '13 at 20:21
  • 2
    $\begingroup$ @vzn: Any $f(n) = o(n)$ is not time constructible (which includes $\alpha(n)$). So the time hierarchy theorem cannot be used here. $\endgroup$ – mdxn Oct 5 '13 at 19:21
  • $\begingroup$ @mdx glad someone pointed that out, just testing you wink. yeah lately have been thinking there might be a generalization of time hierarchy thm for sub-$o(n)$ functions. but anyway the $o(n)$ limit is because a time constructible TM must read all the input, but are we saying these other algorithms eg with inverse Ackermann time complexity dont? having trouble visualizing this! feel the question is more about the existence of sub-$o(n)$ languages.... could there be some kind of survey or description somewhere.... $\endgroup$ – vzn Oct 5 '13 at 19:28
  • 1
    $\begingroup$ @vzn: The OP really needs to clarify what model of computation they have in mind. $\text{DLOGTIME}$ and $\text{LH}$ need to be defined on random access TMs (or equivalents). When specifying our mechanics, we might inadvertently add too much power. It may even be to the extent where the notion of computational complexity is not fruitful. In the most basic terms, we would have to change our notion of time complexity (which is what amortized runtime does) with the risk that such a definition might become very contrived (same goes for the model of computation). $\endgroup$ – mdxn Oct 5 '13 at 19:57
8
$\begingroup$

Seth Pettie came up with an algorithm for computing the sensitivity of a minimum spanning tree in time $O(m\log \alpha(m,n))$, improving on an algorithm of Tarjan which computes the same in time $O(m\alpha(m,n))$. (Compare this to Chazelle's $O(m\alpha(m,n))$ algorithm for computing the minimum spanning tree itself.) The sensitivity problem asks to compute, for a given graph and a given minimum spanning tree, by how much each edge weight can change without changing the minimum spanning tree.

(Thanks to Tsvi Kopelowitz for this reference.)

$\endgroup$
  • 1
    $\begingroup$ I don't know if log inverse Ackermann is "fundamentally slower" than inverse Ackermann, but I found this kind of running time surprising. $\endgroup$ – Yuval Filmus Jan 7 '16 at 20:48
4
$\begingroup$

The most comically slowly-growing function I've ever seriously seen used in a paper is $\alpha^*(n)$, the number of times you have to apply the Ackermann inverse to drop $n$ to some fixed constant. It's used in this paper on the deque conjecture on splay trees.

$\endgroup$
-1
$\begingroup$

When Alan Turing discovered the computer, there used to be several models for the computer proposed. Turing proved that some (3) of these models could simulate each other AND compute the Ackermann function, whereas the other models could simulate each other but not the Ackermann function (so they could not simulate the 3). Therefore, these 3 models (Turing Machine, von Neumann and one I don't know), were chosen as the architecture for a computer. This does not mean the Ackermann function is the limit of the computer, but I suppose it's hard science. I'm not aware of any computable functions that grow faster than the Ackermann function.

Now, I don't think there's a practical problem that matches your question, but perhaps we can construct one. We need to put constraints on the input though. Since we can't use O(n), we cannot check the whole input. In fact, we cannot even check the length of the input as that would be O(log n). So, we need as first parameter a representation of the length of the rest of the input, for example c such that Ackermann(c) is the length of the input. Since this is also not suitable, we demand as first value in our input the parameter c, such that bb(c) is about the length of the input, where bb is the busy beaver function. This function is incomputable but bb(c) certainly exists. Then, the algorithm goes like:

for (int i=0; i<c; i++) {
    if (input[i] == null) {
        return false;
    }
}
return true;

The purpose of the algorithm is to check that if c is the inverse of bb, if then the input length is greater than bb(c).

If there's a computable function that grows faster than the Ackermann function, I think we can use it's inverse to create an algorithm that answers your question on any input.

$\endgroup$
  • $\begingroup$ There definitely exist functions that grow faster than the Ackermann function as pointed out in the comments (TREE(n)). The tricky part of the question is constructing an algorithm with a run-time bound of the inverse of that function. Such a machine does not have enough time to compute the inverse of the function in the first place, so the construction of a TM that achieves this is not straight forward. $\endgroup$ – mdxn Jun 16 '15 at 19:56

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.