Question: Are there any "real-world" examples of computable functions (such as integer multiplication/ matrix multiplication / etc.), where it is known that no asymptotically optimal algorithm exists?

Background: Over the past decades we have seen advancements in algorithms like matrix-multiplication that achieve lower and lower asymptotic computational complexity, such as Strassen's method or the Coppersmith-Winograd algorithm or the recent advance by Alman and Williams; yet, at the same time, besides Strassen none of these algorithms get used in practice since the coefficients get absurdly large, making them so-called Galactic algorithm's.

This raises the question: Are we in a situation where, there exists some lower bound like $\mathcal O(n^{2})$ (or $\mathcal O(n^{2}\log n)$, or $\mathcal O(n^{c})$ or whatever) that can never be achieved, but instead for any particular algorithm we find, there will be another one with a strictly lower asymptotic computational complexity.

It seems plausible that we could keep finding algorithms with complexity $\mathcal O(n^{c+\epsilon})$, yet at the same time the coefficients necessarily blow up as $\epsilon\to 0$. But what would this say about the usefulness of asymptotic complexity in practice? Does it mean that instead of trying to find fast algorithms for the general problem, one should rather spend time trying to find fast algorithms for the bounded problem $n<N$ instead? Do we know for instance know what the fastest 8x8 (32x32 / 128x128 / ...) matrix multiplication algorithm is? For what $n$ do we know what the bilinear-complexity of the $n\times n$ matrix multiplication problem is? Doesn't this mean that, in practical terms, a more fruitful endeavor than finding asymptotically fast $n\times n$ matrix multiplication algorithms, would be to find fast multiplication algorithms for each $n$ individually, and then use a lookup table? To what degree is this even possible (combinatorial explosion) ??


1 Answer 1


This is hard to answer definitively because very few lower bounds are known in complexity theory. But here’s a potentially relevant result: there is no optimal universal code of the natural numbers, where a “universal code” is a map from natural numbers to binary code words such that any list of natural numbers can be uniquely decoded from the concatenation of their code words.

To clarify what we mean by “optimal”: given any universal code, let $p(n)$ be the implied probability of the code word for $n$ ($2^{-k}$ for a word of length $k$). Then there exists a “better” code whose implied probabilities satisfy $\frac{q(n)}{p(n)} \to \infty$.

For example, one universal code is Elias gamma coding, which represents a number $n$ by $\lfloor\log_2 n\rfloor$ zero bits followed by the binary representation of $n$. Its implied probabilities are $2^{-2\lfloor\log_2 n\rfloor - 1} = Θ\bigl(\frac{1}{n^2}\bigr)$. A better universal code is Elias delta coding, whose implied probabilities are $Θ\bigl(\frac{1}{n \log^2 n}\bigr)$.

Given any universal code, one can find a better code. In fact, given any infinite sequence of universal codes, one can find a code that’s better than all of them. One can then ask whether there exists an optimal transfinite chain of universal codes; the answer turns out to be independent of ZFC. See Yuval Filmus, “Universal codes of the natural numbers” (2013).

If there were some function that can be computed in time $Θ\bigl(\frac{1}{p(n)}\bigr)$ for any universal code, it would provide an answer to your question. It’s hard to imagine exactly what such a function might look like, but I don’t see any reason to rule it out.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .